문제

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));
}