BOJ 15989 : 1, 2, 3 더하기 4 [C++]

15989번: 1, 2, 3 더하기 4

 

DP인건 알겠는데 어떻게 점화식을 구해야 할지 오래 고민했다

 

5
1 1 1 1 1
1 1 1 2
1 1 3
1 2 2
2 3

6
1 1 1 1 1 1
1 1 1 3
1 2 3
3 3
1 1 1 1 2
1 1 2 2
2 2 2

7
1 1 1 1 1 1 1
1 1 1 1 3
1 1 2 3
2 2 3
1 3 3
1 1 1 1 1 2
1 1 1 2 2
1 2 2 2

8
1 1 1 1 1 1 1 1
1 1 1 1 1 3
1 1 1 2 3
1 2 2 3
1 1 3 3
2 3 3
1 1 1 1 1 1 2
1 1 1 1 2 2
1 1 2 2 2
2 2 2 2

 

이렇게 써놓으니 3을 더해 N을 만들 수 있는 경우의 수는 N - 3을 만드는 경우의 수와 같다는 것을 금방 알 수 있었다

 

3을 더해 N을 만들 수 있는 경우의 수를 구하는 과정에서 (1, 2, 3) (1, 3) (2, 3), (3)을 써서 N을 만드는 경우의 수는 모두 구해줬다.

 

남은 경우의 수는 (1, 2)와 (1)을 써서 N을 만드는 경우의 수인데, (1)을 써서 N을 만드는 경우의 수는 1개뿐이다

(1, 2)를 사용해 N을 만들 수 있는 경우의 수는, N을 2로 나눈 몫과 같다.

(1과 2만 사용해서 N을 만들 때 2가 최대 N/2개 들어갈 수 있음)

(N이 5라면 1, 2만을 이용해서 5를 만드는 경우는 (1, 1, 1, 2), (1, 2, 2) 두 가지이다.)

 

따라서 점화식을 아래와 같이 구했다.

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

 

테스트 케이스마다 DP값을 구해야 하니 처음부터 N의 최댓값인 10000까지의 경우의 수를 구해놓고 입력이 들어오면 바로 출력하도록 해줬다.

 

코드

#include <iostream>

int T, N;
int dp[10001];

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

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

    while (T--) {
        std::cin >> N;
        std::cout << dp[N] << "\n";
    }
    return 0;
}