[백준 알고리즘] 9095번: 1, 2, 3 더하기 (C++)

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

문제

문제 정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 7가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다.

1+1+1+1 1+1+2 1+2+1 2+1+1 2+2 1+3 3+1 정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오.

입력 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 정수 n이 주어진다. n은 양수이며 11보다 작다.

출력 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다.

풀이

DP 문제는 항상 패턴을 찾아내는게 쉽지 않다. 문제를 보고 고민을 해봤을 때, 규칙이 잘 보이지 않아서 이럴 때 애용하는 방법인 노가다로 n=6까지 나열해보았다. 경우의 수가 좀 많아서 헷갈렸지만 결국 규칙을 찾긴 찾았다.

N에 대해서 만들 수 있는 조합을 모두 찾아보면 위 표와 같다. 그리고 0번째 인덱스를 제외한 수열의 규칙을 찾으면 인데스 4부터는 바로 이전 3개의 아이템을 모두 더한 값이 N번째 값이 된다는 것을 알게되었다. 따라서 이 규칙을 DP에 대입해 일반화시키면

DP[N] = DP[N-1] + DP[N-2] + DP[N-3] , N > 3

을 만들 수 있다. 점화식을 세웠으니 코드만 뚝딱 짜면 끝이다.

구글께서 알려주는 풀이

원래 정석대로면 나처럼 노가다로 푸는게 아니다. 구글링을 통해 알아본 정석대로 세우는 점화식을 정리해보자.

1, 2, 3은 방법의 수가 나와있으니 4로 넘어가보면, 어차피 우리는 항상 1, 2, 3을 사용해야한다. 이때, 1, 2, 3에서 4를 만드려면 1+3, 2+2, 3+1 을 해주면 된다. 따라서, 4를 만드는 방법의 수는

1을 만드는 경우의 수에 3을 더해주는 방법 1번, 2를 만드는 경우의 수에 2번에 각각 2를 더해주는 방법 총 2번, 3을 만드는 경우의 수에 4번에 각각 1을 더해주는 방법 4번을

모두 더한 7번이 된다. 대박적.

코드

#include<iostream>

using namespace std;

int dp [11] = {0};

int main (){
    int T;
    cin >> T;

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

    while(T--){
        int n; 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;
}