문제
풀이
1을 만드는 경우의 수는 1 가지, 2는 2 가지, 3은 4 가지의 경우의 수를 갖습니다.
4를 만드는 경우의 수는 단순히 1에서 3을 더한 경우, 2에서 2를 더한 경우, 3에서 1을 더한 경우의 수를 모두 더해주면 됩니다.
5도 마찬가지로 2에서 3을 더한 경우, 3에서 2를 더한 경우, 4에서 1을 더한 경우의 수를 더하면 5를 만드는 경우의 수를 구할 수 있겠죠?
그러면 다음과 같은 점화식이 도출됩니다.
1
cache[i] = cache[i-1] + cache[i-2] + cache[i-3]
i 가 1,2,3인 경우는 따로 처리해줘야 합니다.
DP 문제는 반복문이나 재귀 함수로 풀 수 있습니다. 저는 재귀 함수가 좀 더 깔끔해서 재귀함수로 푸는 것을 선호합니다.
반복문 사용
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <iostream>
#include <vector>
using namespace std;
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int T, n;
cin >> T;
vector<int> dp(12, 0);
dp[1] = 1;
dp[2] = 2;
dp[3] = 4;
for (int i = 4; i < 12; i++)
dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3];
for (int i = 0; i < T; i++)
{
cin >> n;
cout << dp[n] << '\n';
}
return 0;
}
재귀 사용
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include <iostream>
#include <vector>
#include <cstring> // memset
using namespace std;
int n;
int cache[12];
int recur(int num)
{
// 기저 사례
if (num == 1)
return 1;
if (num == 2)
return 2;
if (num == 3)
return 4;
// 메모이제이션
if (cache[num] != -1)
return cache[num];
return cache[num] = recur(num - 1) + recur(num - 2) + recur(num - 3);
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int T;
cin >> T;
while (T--)
{
cin >> n;
// 캐시를 -1로 초기화
memset(cache, -1, sizeof(cache));
cout << recur(n) << '\n';
}
return 0;
}
