문제

https://www.acmicpc.net/problem/1697

풀이

수빈이가 좌표 N에서 동생이 있는 좌표 K를 찾아가야하는데 수빈이가 동생을 찾는 가장 빠른 시간, 즉 최소 비용을 찾는 문제다. 수빈이는 걷거나 순간 이동을 할 수 있는데 수빈이의 현재 좌표를 X라 할때 X+1, X-1, X*2로 이동할 수 있으며 모든 동작에는 1초의 시간이 걸린다고 한다. 최소 비용을 찾고, 모든 정점의 가중치가 1(초)로 똑같기 때문에 BFS로 해결 할 수 있다. 풀면서 아래의 조건을 체크하여 반복 횟수를 줄였다.

1. (당연하지만) 한번 방문한 정점은 다시 안가도 된다. 
2. 최소 비용이 될 수 있는 후보 중 가장 작은 값보다 현재 비용이 크다면 바로 답이 아니라 간주한다.

#include <cstdio>
#include <queue>
using namespace std;
struct movement{
	int x,step;
};
queue<movement> q;
int visit[100001] = {0};
int abs(int x) {return x>0?x:-x;}
int main(){
	int n,k,i,ans;
	movement move;
	
	scanf("%d%d",&n,&k);
	move.x = n;
	move.step = 0;
	
	ans=abs(n-k);

	if(n >= k){
		printf("%d",ans);
		return 0;
	}

	q.push(move);
	while(!q.empty()){
		q.front();
		
		if(q.front().step >= ans){
			q.pop();
			continue;
		}

		if(q.front().x == k) {
			ans = q.front().step;
			q.pop();
			continue;
		}

		move.step = q.front().step + 1;

		if(q.front().x*2 <= 100000 && q.front().x*2 >= 0 && !visit[q.front().x*2]){
			move.x = q.front().x * 2;
			visit[move.x] = 1;
			q.push(move);
		}

		if(q.front().x +1 <= 100000 && !visit[q.front().x+1]) {
			move.x = q.front().x + 1;
			visit[move.x] = 1;
			q.push(move);
		}
		if(q.front().x - 1 >= 0 && !visit[q.front().x-1]){
			move.x = q.front().x - 1;	
			visit[move.x] = 1;
			q.push(move);
		}
		q.pop();
	}
	printf("%d",ans);
}

문제

https://www.acmicpc.net/problem/1904

풀이

1과 00만을 이용한 길이가 N인 이진 수열이 몇개인지 찾는 문제이다. 1과 00만을 사용해야 해야하므로 0이 혼자 쓰여서는 안된다. 이 문제는 직접 몇 개의 케이스를 손으로 적어서 풀었다.

DP[1] = 1

DP[2] = 11, 00

DP[3] = 111, 100, 001

DP[4] = 1111, 1100, 1001, 0011, 0000

DP[5] = 11111, 11001, 10011, 10000, 00001, 00100, 00111, 01001

...

길이가 N일때의 갯수를 세어보면 $ DP[N] = DP[N-1] + DP[N-2] $, 즉 이 문제는 단순한 N번째 피보나치 수를 구하는 문제와 같다.

#include <stdio.h>
int dp[1000001];
int solve(int x){
	if(dp[x]) return dp[x];
	return dp[x] = (solve(x-1) + solve(x-2)) % 15746;
}
int main() {
	int n;
	dp[1] = 1;
	dp[2] = 2;
	dp[3] = 3;
	scanf("%d",&n);
	printf("%d",solve(n));
}

문제

https://www.acmicpc.net/problem/1963

풀이

나는 가장 먼저 이 문제는 정해진 범위의 소수만을 다루면서 여러 테이스 케이스를 입력받기 때문에 미리 소수를 판별하는 테이블을 만들어 놓았다. 그리고 현재 비밀번호와 현재 비밀번호까지 오는데 몇 번이나 거쳤는지 저장하기 위해 change라는 구조체를 만들어 <queue>에 넣고 1000의 자리부터 1의 자리까지 모두 0~9를 대입하며 큐에 넣고 방문했다는 표시를하여 다시 그 수로 돌아오지 못하게 하여 최소 경로를 찾게 하였다.

#include <cstdio>
#include <cmath>
#include <queue>
using namespace std;
struct change{
	int pw,step;
};
int prime[10000]={0};
int main(){
	int t,i,j;
	double sq;
	scanf("%d",&t);
	for(i=1000;i<=9999;i++){
		sq = sqrt((double)i);
		for(j=2;j<=sq;j++){
			if(i%j==0){
				prime[i] = 1;
				break;
			}
		}
	}
	while(t--){
		int visit[10000] = {0};
		queue<change> q;
		change chg;
		int from,dest,digit,rest,ans=987654321;
		scanf("%d%d",&from,&dest);
		chg.pw = from;
		chg.step = 0;
		visit[from] = 1;
		q.push(chg);
		while(!q.empty()){
			if(q.front().step >= ans){
				q.pop();
				continue;
			}
			if(q.front().pw == dest){
				ans = q.front().step;
				q.pop();
				continue;
			}
			for(i=1;i<=1000;i*=10){
				rest = q.front().pw - ((q.front().pw / i) % 10) * i;
				for(j=0;j<=9;j++){
					if(i==1000&&!j) continue;
					if(prime[j*i+rest]||visit[j*i+rest]) continue;
					chg.pw = j*i+rest;
					chg.step = q.front().step + 1;
					q.push(chg);
					visit[chg.pw] = 1;
				}
			}
			q.pop();
		}
		printf("%d\n",ans);
	}
}

문제

https://www.acmicpc.net/problem/1004

풀이

문제를 요약하자면 시작점과 도착점의 좌표가 주어지고, 여러 원의 좌표와 반지름이 주어질때 시작점에서 도착점까지 도달하는데 최소로 원을 통과하는 횟수를 출력해야 하는 문제이다.

만약 임의의 원 C에 대해 시작점과 도착점이 둘다 안쪽에 있거나 바깥쪽에 있는 경우에는 해당 원을 거칠 필요가 없다는 뜻이므로 카운팅하지 않아도 된다. 즉, 시작점이 안쪽에 있고 도착점이 바깥쪽에 있거나 그 반대의 경우에만 카운팅을 해주면 최소 횟수를 구할수가 있는데 좌표 P가 C 내부에 있는지 이는 피타고라스의 정리를 사용하여 쉽게 판별할수있다.

우리는 시작점과 도착점이 서로 다를 경우에만 카운팅을 해주면 되므로 두 점을 판별한 결과값의 xor 연산 결과가 참일때만 카운트 해주면 된다.

#include <stdio.h>
int isInCircle(int x,int y, int Cx, int Cy, int Cr){
    return (x-Cx)*(x-Cx) +(y-Cy)*(y-Cy)<Cr*Cr;
}
int main(){
	int t,i;
	scanf("%d",&t);
	while(t--){
		int x1,y1,x2,y2,n,cx,cy,r,c=0;
		scanf("%d%d%d%d%d",&x1,&y1,&x2,&y2,&n);
		for(i=0;i<n;i++){
			scanf("%d%d%d",&cx,&cy,&r);
			c += isInCircle(x1,y1,cx,cy,r) ^ isInCircle(x2,y2,cx,cy,r);
		}
		printf("%d\n",c);
	}
}

문제

https://algospot.com/judge/problem/read/HAMMINGCODE

풀이

단순한 구현문제. 입력이 7자리의 바이너리이므로 char로 받은뒤 int 배열에 넣고 xor을 사용해 syndrome 값을 구했다.

#include <stdio.h>
int main(void) {
	int t;
	scanf("%d",&t);
	while(t--){
		int i, syn = 0,encoded[8];
		char c;
		for(i=1;i<=7;i++){
			scanf(" %c",&c);
			encoded[i] = c-'0';
		}
		syn += ((encoded[1] ^ encoded[3]) ^ encoded[5]) ^ encoded[7];
		syn += 2 * (((encoded[2] ^ encoded[3]) ^ encoded[6]) ^ encoded[7]);
		syn += 4 * (((encoded[4] ^ encoded[5]) ^ encoded[6]) ^ encoded[7]);
		encoded[syn] ^= 1;
		printf("%d%d%d%d\n",encoded[3],encoded[5],encoded[6],encoded[7]);
		
	}
	return 0;
}