boj 15989 1, 2, 3 더하기 4

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

15989번: 1, 2, 3 더하기 4

 

제 개인적으로는 생각을 좀 해봐야했던 dp문제였습니다 ㅠㅠ.. 오래안해서 다죽은듯..

 

처음에는 방법의 수를 하나하나 나열해봤지만 해답을 찾을수 없었는데..

 

1, 2, 3으로 나타내는 방법의 수를 나누는 방법을 생각해보았습니다.

1. 1이하의 수로 나타내는 방법

2. 2이하의 수로 나타내는 방법

3. 3이하의 수로 나타내는 방법

으로 나눌 수 있습니다.

 

1이하로 나타내는 방법은 i - 1번째의 1이하로 나타내는 방법과 같습니다.

2이하로 나타내는 방법은 i - 2번째의 1이하로 나타내는 방법 + 2이하로 나타내는 방법입니다.

3이하로 나타내는 방법은 i - 3번째의 1이하로 나타내는 방법 + 2이하로 나타내는 방법 + 3이하로 나타내는 방법입니다.

 

따라서 dp[0][N], dp[1][N], dp[2][N]을 모두 더한 값이 답이 되겠습니다.

 

 

#include <iostream>
using namespace std;
 
int dp[3][10001];
 
void init() {
    dp[0][1] = 1;
    dp[0][2] = 1;
    dp[1][2] = 1;
    dp[0][3] = 1;
    dp[1][3] = 1;
    dp[2][3] = 1;
    for (int i = 4; i <= 10000; i++) {
        dp[0][i] = dp[0][i - 1];
        dp[1][i] = dp[0][i - 2] + dp[1][i - 2];
        dp[2][i] = dp[0][i - 3] + dp[1][i - 3] + dp[2][i - 3];
    }
}
 
int main() {
    cin.tie(NULL); cout.tie(NULL);
    ios::sync_with_stdio(false);
 
    init();
    int tc, N;
    cin >> tc;
    while (tc--) {
        cin >> N;
        cout << dp[0][N] + dp[1][N] + dp[2][N] << '\n';
    }
 
    return 0;
}