Info

---

• 백준 15989번 1, 2, 3 더하기 4
• Silver 1 solved.ac
• 다이나믹 프로그래밍

Write UP

---

1, 2, 3을 사용해서 입력값을 표현하는 방법의 수를 찾아야 해요.
단, 사용한 숫자의 갯수가 중복되면 안됩니다. 1+1+2, 1+2+1을 똑같은 경우로 생각한다는 거예요.

처음 이 문제를 풀 땐 dfs로 접근했습니다.
1~3 사이의 반복문을 돌며 재귀로 완전탐색, 방문한 노드는 visited 처리를 해서 중복을 제거하고 백트래킹까지..
이렇게 열심히 구했는데 시간초과가 떴습니다ㅠㅠ

따라서 DP로 접근 방법을 바꿨어요.

다이나믹 프로그래밍의 핵심은 어떻게 dp 배열을 잡아야 할지 정하는 거잖아요?
이렇게 잡아봅시다.

d[i][0] : 1로 시작하고, 1보다 작거나 같은 수를 사용해서 i 를 만드는 경우
d[i][1] : 2로 시작하고, 2보다 작거나 같은 수를 사용해서 i 를 만드는 경우
d[i][2] : 3으로 시작하고, 3보다 작거나 같은 수를 사용해서 i 를 만드는 경우

구해준 후 세 값을 더하면 모든 경우의 수가 구해지겠죠?
하나씩 써보면서 점화식을 유도해봅시다.

일단 모든 d[i][0] 은 당연히 1이니 생략합시다.

i = 2일 때, d[2][1]도 1입니다.
i = 3일 때, d[3][1]과 d[3][2]도 1입니다. (3, 2+1, 1+1+1)

여기까진 쉽게 구할 수 있으니, i = 4부터 일반화를 해볼게요.

d[4][1]은 2로 시작하고 2보다 작거나 같은 수를 사용해서 4를 만드는 경우죠?
2+2, 2+1+1 이 있겠네요.

그런데 맨 앞에 2를 떼면 (2, 1+1)이고, 이는 곧 d[2][0] + d[2][1]과 같습니다.

따라서 d[i][1] = d[i-2][0] + d[i-2][1]이 돼요.

이제 d[4][2]를 봅시다. 3으로 시작하는 경우는 (3+1) 밖에 없어요.

이 친구는 d[1]의 모든 경우의 수와 같아요. i = 6까지 가보면 증명이 됩니다.

따라서 d[i][2] = d[i-3][0] + d[i-3][1] + d[i-3][2]가 성립해요.

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

int N;
int dp[10004][3];

// dp[i][0]: 1로 시작하는 경우
// dp[i][1]: 2로 시작하는 경우
// dp[i][2]: 3으로 시작하는 경우

int main() {
    int t;
    scanf("%d", &N);
    dp[1][0] = 1;
    dp[2][0] = 1;
    dp[2][1] = 1;
    dp[3][0] = 1;
    dp[3][1] = 1;
    dp[3][2] = 1;
    
    for (int i = 4; i < 10001; i++) {
        dp[i][0] = 1;
        dp[i][1] = dp[i-2][0] + dp[i-2][1];
        dp[i][2] = dp[i-3][0] + dp[i-3][1] + dp[i-3][2];
    }
    
    while (N--) {
        scanf("%d", &t);
        printf("%d\n", dp[t][0]+dp[t][1]+dp[t][2]);
    }
    
    return 0;
}

4/14 추가++

---

사실 이렇게 할 필요가 없던 문제였어요..

dp[i]를 i를 만드는 경우의 수로 잡고 1, 2, 3 순서대로 dp 테이블에 넣어주면 끝이었습니다.

코드를 보면서 설명을 덧붙일게요.

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

int T, N;
int dp[10004];
int arr[24];

void init() {
    for (int i = 0; i < 10004; i++) {
        dp[i] = 0;
    }
}

int main() {
    scanf("%d", &T);
    while (T--) {
        init();
        scanf("%d", &N);
        dp[0] = 1;
        for (int i = 1; i <= 3; i++) {
            for (int j = i; j <= N; j++) {
                dp[j] += dp[j-i];
            }
        }
        printf("%d\n", dp[N]);
    }
    return 0;
}

첫 번째 반복문에서, i의 범위는 1, 2, 3이에요.
이 숫자들을 가지고 만들어야 하니깐 순서대로 넣어줬습니다.

i = 1일 때를 생각해봅시다.
j = 1 ~ N 까지 돌아요. dp[j] += dp[j-1]이 실행되니깐 모든 테이블에 1이 들어갑니다.
말로 풀어쓰면, j를 1만 써서 만들기 위한 경우의 수예요.

i = 2로 넘어왔어요.
짚고 넘어가야 할 것은 이미 dp테이블에 1을 써서 만든 경우의 수가 들어있다는 것입니다.
때문에 dp[j-2]를 더해주면 중복없이 2로 시작하는 경우의 수를 따질 수 있어요.
계속 더해주니깐 테이블이 갱신되면서 쌓이게 됩니다.

이 아이디어를 빠르게 떠올릴 수 있도록 더 공부해야겠어요ㅠㅠ