[BOJ] 12101 : 1,2,3 더하기 2 - travelbeeee

문제 : https://www.acmicpc.net/problem/12101

---

[ 알고리즘풀이 ]

1. DP[X] : X를 1, 2, 3을 이용해서 표현할 수 있는 경우의 수.

→ DP[X] = DP[X - 1] + DP[X - 2] + DP[X - 3]

2. N, K 가 입력되면 DP[N] 값과 K를 비교해 나올 수 없는 경우 -1을 출력하고,

아니라면 K를 DP[N - 1], DP[N - 2], DP[N - 3] 과 비교해서 1, 2, 3 중 해당되는 값을 재귀적으로 출력한다.

#include<iostream>

using namespace std;

int N, K, dp[11] = { };

void printAnswer(int N, int K) {
	if (dp[N] < K){
		cout << -1;
		return;
	}
	for (int i = 1; ; i++) {
		if (dp[N - i] >= K) {
			if (N - i > 0){
				cout << i << '+';
				printAnswer(N - i, K);
			}
			else
				cout << i;
			break;
		}
		K -= dp[N - i];
	}
	return;
}

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);

	cin >> N >> K;
	
	dp[0] = 1, dp[1] = 1, dp[2] = 2, dp[3] = 4;
	for (int i = 4; i < 11; i++)
		dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3];

	printAnswer(N, K);
	return 0;
}

---