문제 풀이

정수 1을 1, 2, 3으로 나타내는 방법은
1
로 1개 이고
정수 2를 1, 2, 3으로 나타내는 방법은
1 + 1
2
로 2개 이고
정수 3을 1, 2, 3으로 나타내는 방법은
1 + 1 + 1
2 + 1
1 + 2
3
으로 4개 이다.

4부터는 d[i-3]에서 각각에 3을 덧붙여 주면 되고, d[i-2]에서 각각 2를 덧붙여 주면되고, d[i-1]에서 각각 1을 덧붙여 주면된다.
즉 점화식은 $d[i] = d[i-1] + d[i-2] + d[i-3]$ 이 된다.

문제 링크

boj/15988

소스코드

PS/15988.cpp

#include <iostream>
#include<vector>
#include<algorithm>
#include<math.h>
#include<queue>

using namespace std;

int main() {
	int n, a, b;
	cin >> n >> a >> b;
	int cnt = 0;
	while (a != b)
	{
		if (a % 2)
		{
			a /= 2;
			a += 1;
		}
		else
		{
			a /= 2;
		}
		if (b % 2)
		{
			b /= 2;
			b += 1;
		}
		else
			b /= 2;
		cnt++;
	}
	cout << cnt;
}