백준(BOJ) 9095 1, 2, 3 더하기 C++ 풀이

문제 링크: https://www.acmicpc.net/problem/9095

9095번: 1, 2, 3 더하기

문제 풀이에 이용된 알고리즘: DP

 

굉장히 쉬운 DP 문제이다.

 

DP는 알고 풀면 너무 쉽고, 모르고 풀면 한 없이 어려워서 다음과 같은 질문이 떠오를 것이다.

 

1. 왜 쉽냐? --> 음... 비슷한 유형을 풀어봐서, "알고 풀었기" 때문이라고 밖에 말씀드릴 수 없을 것 같다...

 

2. 왜 DP냐? --> "큰 문제를 해결할 때, 그 큰 문제 구성하는 더 작은 단위의 해답이 이용될 수 있기 때문"이라는 원론적인 이야기 밖에 할 수 없을 것 같다...

 

결론은, DP는 실버 1 이하의 여러가지 문제를 최대한 많이 반복적으로 풀어보는 것이 좋다고 생각된다.

 

문제를 풀이하면 다음과 같다.

 

어떤 수 n을 1, 2, 3의 합으로 표현할 수 있는 모든 경우의 수를 파악하는 문제이다.

 

문제에 주어진 예시처럼, 4를 표현하는 방법은 7가지이다. 3을 표현하는 1 + 2와 2 + 1은 서로 다른 하나로 친다.

 

주황색으로 하이라이트 강조한 부분이, 점화식을 세울 때 사람을 헷갈리게 한다.

 

이전 항에 2배를 해줘야 하나...? 아 근데 이전 항의 이전 항에서도 중복되는 조합이 발생하는데...?

 

그렇지만 1부터 차근 차근 살펴보면 다음과 같이 쉽게 풀린다.

 

먼저, 1은 1 하나로 표현 가능하다. 즉, dp[1] = 1이다.

 

2는 1 + 1과 2로 표현 가능하다. 1 + 1과 2, 두 경우 모두 좌우로 뒤집거나 구성 숫자의 순서를 바꿀 수 없으므로 더 이상 고려할 필요 없이 dp[2] = 2이다.

 

3은 1 + 1 + 1과 1 + 2, 2 + 1, 3 이렇게 4가지로 표현 가능하다. 1 + 2와 2 + 1은 구성 숫자는 같지만 그 순서가 다르다.

 

4는 || 1 + 1 + 1 + 1 || 1 + 2 + 1 || 2 + 1 + 1 || 3 + 1 || 1 + 1 + 2 || 2 + 2 || 1 + 3 || --> 총 7가지가 된다.

 

||는 단순한 구분선인데, 특이한 점을 찾았는가?

 

보통 4를 구성하는 모든 경우의 수를 적으라고 하면 다음과 같이 적을 것이다.

 

|| 1 + 1 + 1 + 1 || 1 + 1 + 2 || 1 + 2 + 1 || 2 + 1 + 1 || 1 + 3 || 3 + 1 || 2 + 2 ||

 

뭔가 순서만 다른 유사한 녀석들끼리 인접해 있어서, 떠올리기 편하기 때문에 위처럼 적는 것이 당연하다.

 

이 문제를 푸는 방법은 이러한 이상한 점에 있다.

 

n이라는 숫자를 1, 2, 3의 합으로 구성하는 방법을 dp[n]이라고 한다면, n보다 3작은 수를 구성하는 조합에 추가적으로 3d을 더하면 n이 된다.

 

마찬가지로 n보다 2작은 수를 구성하는 조합에 2를 더한다면 그 결과는 n이 된다.

 

n보다 1작은 수를 구성하는 조합에 1을 더한다면 그 결과는 n이 된다.

 

즉 dp[n] = dp[n-3] + dp[n-2] + dp[n-1]이 된다.

 

이 규칙을 4에 대해서 한번 더 적용하여 자세히 풀어 작성하면 다음과 같다.

 

1 --> || 1 || --> (여기에 3을 추가적으로 더하면) || 1 + 3 ||

2 --> || 1 + 1 || 2 || --> (여기에 2를 추가적으로 더하면) || 1 + 1 + 2 || 2 + 2 ||

3 --> || 1 + 1 + 1 || 1 + 2 || 2 + 1 || 3 || --> (여기에 1을 추가적으로 더하면) || 1 + 1 + 1 + 1 || 1 + 2 + 1 || 2 + 1 + 1 || 3 + 1 ||

 

이런 식으로 더해나가면 dp[n]을 쉽고 빠르게 구할 수 있다.

 

이전 항에 1을 더하고, 거기서 발생하는 있는 추가적인 조합을 또 곱해줘야 하나....? 등등의 고민이 필요없었다는 것을 알 수 있다.

 

#include <iostream>
 
using namespace std;
 
int t, T, n, dp[11];
 
int main()
{
    dp[1] = 1, dp[2] = 2, dp[3] = 4;
 
    cin >> T;
 
    for (t = 1; t <= T; t++)
    {
        cin >> n;
        for (int i = 4; i <= n; i++)
            dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3];
 
        cout << dp[n] << endl;
    }
 
    return 0;
}