[C++] 백준 15989번: 1, 2, 3 더하기 4

🔗 문제

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

✏️ 풀이

 

이 문제가 어려운 이유는 중복 순서가 허용되지 않기 때문이다. 

 

당연히 숫자를 바텀업 방식으로 이전의 숫자를 만드는 방법을 활용해야겠다는 생각이 든다. 

이게 바로 dp 구나 깨닫는 과정 같은데 점화식 만드는 게 쉽지 않다. 

 

나는 이 문제를 완전 탐색으로도 못 짜겠어서 고생을 했다!

그래도 문제가 1, 2, 3으로만 이루어져 있다는걸 생각하면 활용할 수 있다. 

 

이 문제는 점화식을 만드는 과정이 아니라 설명을 하는게 맞는 것 같다. 

DP.resize(MAX, vector<int>(4, 0)); // 1, 2, 3 인덱스를 사용하기 위한 사이즈 조정

DP[0][1] = DP[1][1] = DP[2][1] = DP[2][2] = 1; // bottom-up을 위한 초기 설정

for(int i=3; i<MAX; ++i)
{
    DP[i][1] = DP[i - 1][1];
    DP[i][2] = DP[i - 2][1] + DP[i - 2][2];
    DP[i][3] = DP[i - 3][1] + DP[i - 3][2] + DP[i - 3][3];
}

 

DP[i][k] : i번째 숫자를 만드는 구성 요소가 마지막 숫자가 k인 "경우의 수"

 

 

우리가 구해야할 숫자가 4라고 했을 때, 각 DP에 들어갈 수 있는 방법은 아래와 같다. 

• DP[4][1] : {1, 1, 1, 1}
• DP[4][2] : {1, 1, 2}, {2, 2}
• DP[4][3] : {1, 3}

그래서 정답은 DP[4][1] + DP[4][2] + DP[4][3]이 된다. 

 

그럼 이 DP의 값은 어떻게 채우느냐? 

k에 1이 들어가기 위해서 DP[i-1]값이 필요하고,

k에 2가 들어가기 위해서는 DP[i-2]값이 필요하다. 

식을 보면 k보다 큰 값은 더하지 않기 때문에 오름차순을 지켜 중복 순서가 허용되지 않는다.

 

💾  소스

#include <iostream>
#include <vector>
using namespace std;

const int MAX = 10001;
vector<vector<int>> DP;

void solve()
{
    DP.resize(MAX, vector<int>(4, 0));
    DP[0][1] = DP[1][1] = DP[2][1] = DP[2][2] = 1;

    for(int i=3; i<MAX; ++i)
    {
  		DP[i][1] = DP[i - 1][1];
  		DP[i][2] = DP[i - 2][1] + DP[i - 2][2];
  		DP[i][3] = DP[i - 3][1] + DP[i - 3][2] + DP[i - 3][3];
    }

}

int main() 
{
    int T, n;
    cin >> T;
    
    solve();
    
    while(T--)
    {
        cin >> n;
        cout << DP[n][1] + DP[n][2] + DP[n][3]  << "\\n";
    }
    
    return 0;
}