[백준] 1, 2, 3 더하기 4 (C++)

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

 

DP는 언제나 너무 어렵다... 내가 바보인것도 있지만 DP 배열을 1차원으로 둘지 2차원으로 둘지 파악하는 것도 매우 까다롭다. 요즘 코딩테스트에서는 DP가 많이나오진 않는 것 같은데 그래도 연습이 필요하다.

 

이 문제는 1, 2, 3으로 N을 만들 수 있는지 물어보는 전형적인 DP문제이다. 

 

당연히 1차원 배열로 풀어보려 했는데 잘 안되서 구글링을 통해 찾아봤다. 상상치도 못한 2차원 배열이 나왔다.

 

dp[i][1] = 1로 만들 수 있는 경우의 수

dp[i][2] = 2를 포함하여 만들 수 있는 경우의 수

dp[i][3] = 3을 포함하여 만들 수 있는 경우의 수

 

이렇게 모아놓는 방식이었다. 이렇게 하는 이유는 1 + 1 + 2, 1 + 2 + 1, 2 + 1 + 1 이 다르게 처리되기 때문이다. 각 수식에다가 각 숫자를 더했을 때 경우의수가 되고 결국은 이전의 숫자에 첨가할 수 밖에 없다는 것을 알아채는 것이 관건인 문제였다.

 

#include <iostream>

using namespace std;
int dp[10001][4];

int main(){
    dp[1][1] = 1;
    dp[1][2] = 0;
    dp[1][3] = 0;

    dp[2][1] = 1;
    dp[2][2] = 1;
    dp[2][3] = 0;

    dp[3][1] = 1;
    dp[3][2] = 1;
    dp[3][3] = 1;

    for(int i = 4; i < 10001; i++){
        dp[i][3] = dp[i - 3][1] + dp[i - 3][2] + dp[i - 3][3];
        dp[i][2] = dp[i - 2][1] + dp[i - 2][2];
        dp[i][1] = dp[i - 1][1];
    }

    int T; cin >> T;

    for(int t = 0; t < T; t++){
        int n; cin >> n;

        cout << dp[n][1] + dp[n][2] + dp[n][3] << '\n';
    }
}