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

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

 

dp 문제이다. 1,000,000 보다 작거나 같은 양수 n은 1, 2, 3의 합으로 표현할 수 있다.

 

단, 합을 나타낼 때는 수를 1개 이상 사용해야 하며 n이 만일 4일 경우 dp[4]는

1 + 1 + 1 + 1

2 + 1 + 1

1 + 2 + 1

1 + 1 + 2

2 + 2

3 + 1

1 + 3 로 총 7가지 이다.

 

dp[3]의 경우

1 + 1 + 1

2 + 1

1 + 2

3 총 4가지 이며

 

dp[2]는

1 + 1

2 총 2가지 이다. 

 

dp[5]까지만 살펴보자면

1 + 1 + 1 + 1 + 1

2 + 1 + 1 + 1

1 + 2 + 1 + 1

1 + 1 + 2 + 1

1 + 1 + 1 + 2

3 + 1 + 1

1 + 3 + 1

1 + 1 + 3

2 + 2 + 1

2 + 1 + 2

1 + 2 + 2

3 + 2

2 + 3

총 13가지이다.

규칙을 살펴 보자면 dp[5]는 전에 있었던 dp[4]에 맨 오른쪽에 1을 더한것 7 + dp [3]에 맨 오른쪽에 2를 더한것 4 + dp[2]에 맨 오른쪽에 3을 더한것 2 해서 7 + 4 + 2 = 총 13가지 인것을 알 수 있다. 따라서 식으로 정리해보면

dp[i] = dp[i-1] + dp[i-2] + dp[i-3]

 

초기값 세개를 넣어주고 4부터 max까지 for문을 돌려서 dp배열을 완성해 준 뒤 출력해주는 형식으로 코드를 짜보았다.

 

#include <iostream>
#include <algorithm>
#define MAX 1000001
#define MODULER 1000000009
using namespace std;
long long dp[MAX] = { 0, };
 
int main(int argc, char* argv[])
{
    int test_case;
    cin >> test_case;
 
    dp[1] = 1;
    dp[2] = 2;
    dp[3] = 4;
    dp[4] = 7;
 
    for (int i = 5;i < MAX;i++) {
        dp[i] = (dp[i - 1] + dp[i - 2] + dp[i - 3]) % MODULER;
    }
 
    for (int T = 1;T <= test_case;T++) {
        int n;
        cin >> n;
        cout << dp[n] << '\n';
    }
 
    return 0;
}

 

1차 실패 dp값을 만들때 수의 제한 때문에 1000000009로 나누어 주어야 하는데 빼먹었다.

 

2차 실패 dp 전체 값을 나누어 주어야 하는데 실수로 괄호를 쓰지 않았다. 

 

3차 성공!

 

다 풀어놓고 쓸데없는데에 힘빼는건 여전하다..