56. C++ 백준 9095 번 자세한 설명

안녕하세요. 코딩하는 덕구입니다. C++ 백준 9095 번 1, 2, 3 더하기 입니다.

다이나믹 프로그래밍 문제입니다.

규칙을 단순히 찾는 것에 그치지 않고, 어째서 이러한 규칙이 나왔는지 자세히 설명하고자 합니다.

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

9095번: 1, 2, 3 더하기

 

 

base cases : 1,2,3 을 1,2,3의 합으로 나타낼 수 있는 경우의 수는 직접 셌습니다.

1 은 1 가지 (1)

2 는 2가지 (1+1, 2)

3은 4가지 (1+1+1, 1+2, 2+1, 3)

4부터는 규칙을 위의 base cases를 이용해서 구할 수 있습니다.

 

전체적인 규칙 설명 드리겠습니다.

4 를 1, 2, 3 의 합으로 표현할 수 있는 경우의 수. 즉 4 = 1+3, 2+2, 3+1 임

1+ 3 (4) //1 + 3 = 4임 괄호 안은 3을 1,2,3으로 표현할 수 있는 경우의 수
2+ 2 (2) //2 + 2 = 4임 괄호 안은 2를 1,2,3으로 표현할 수 있는 경우의 수
3+ 1 (1) //3 + 1 = 4임 괄호 안은 1을 1,2,3으로 표현할 수 있는 경우의 수

즉 4를 1,2,3의 합으로 표현할 수 있는 경우의 수는 4+2+1 = 7 임

5 를 1, 2, 3 의 합으로 표현할 수 있는 경우의 수
1+4 (7) //아까 위에서 4를 1,2,3의 합으로 표현할 수 있는 경우의 수를 구함
2+3 (4) 
3+2 (2)
------ 1, 2, 3 의 합으로 표현하므로 더하지 않아도 됨 
4+1 (1)

6 를 1, 2, 3 의 합으로 표현할 수 있는 경우의 수
1+5 (13) //아까 위에서 5를 1,2,3의 합으로 표현할 수 있는 경우의 수를 구함
2+4 (7)
3+3 (4)
------ 1, 2, 3 의 합으로 표현하므로 더하지 않아도 됨 
4+2 (2)
5+1 (1)

즉 4를 1, 2, 3 의 합으로 표현하는 경우의 수를 구하기 위해서는

1을 1, 2, 3 의 합으로 표현하는 경우의 수  코드에서는 cnt[1] = 1 (1),

2를 1, 2, 3 의 합으로 표현하는 경우의 수  코드에서는 cnt[2] = 2,  (1+1, 2),

3을 1, 2, 3 의 합으로 표현하는 경우의 수  코드에서는 cnt[3] = 4, (1+1+1, 1+2, 2+1, 3),

1+2+4 = 7 이 됩니다.

 

만약 5라면?

4를 1,2,3 의 합으로 표현하는 경우의 수. 방금 구했죠, 즉 7

3을 1, 2, 3 의 합으로 표현하는 경우의 수. 즉 4

2를 1, 2, 3 의 합으로 표현하는 경우의 수. 즉 2

7 + 4 + 2 = 13이 됩니다.

 

왜 여기선 1을 1, 2, 3 의 합으로 표현하는 경우의 수까지 더하지 않느냐는 물음이 생기실텐데,

5 는 

1+4

2+3

3+2

--------------------------

4+1 

4가지로 표현이 가능한데  1,2,3으로 표현할 수 있는 부분들은 더했고

4의 합이 아닌 1, 2, 3 까지의 합으로만 표현하면 되기에 더 하시면 안됩니다.

즉 점화식으로 나타내면 n>3 이고 정수 일때

dp(n) = dp(n-1) + dp(n-2) + dp(n-3) 이 됩니다. 

코드로 나타내면

cnt[n] = cnt[n-1] +cnt[n-2] + cnt[n-3] 

 

백준 9095 번 C++ 최종 코드입니다.

위의 설명을 천천히 잘 따라오신다면 쉽게 이해하실 수 있으실 겁니다.

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

굳이 n>3 의 조건을 넣지 않은 이유는 cnt를 초기화 할때

cnt[1], cnt[2], cnt[3]의 값 들을 넣어주었기 때문에

정상적으로 출력이 되기 때문입니다.

C++ 백준 9095 번 이였습니다. 감사합니다.