[C++] 백준 온라인 저지 9095번 1, 2, 3 더하기 풀이

 

정수가 주어질 때 주어진 정수를 1, 2, 3의 합으로 나타낼 수 있는 경우의 수를 구하는 문제

 

---

문제의 조건

 

1. 합을 나타낼 때엔 1개 이상의 수를 사용해야 한다. 

 

정수 4를 1, 2, 3의 합으로 나타낸다면 다음과 같은 방법들로 나타낼 수 있다. 

• 1+1+1+1
• 1+1+2
• 1+2+1
• 2+1+1
• 2+2
• 1+3
• 3+1

 

2. 주어지는 정수는 양수이며 11보다 작다. 즉 1 ~ 10 사이 숫자만 나온다. 

 

3. 첫째줄에 테스트 케이스의 갯수 T가 주어지며 다음 줄부터 T 갯수만큼 한 줄마다 정수가 주어진다. 

 

 

풀이 과정

 

DP를 연습하려고 푼 문제인데 아직 DP를 잘 못 해서 문제를 봤을 땐 당연히 풀이가 떠오르지 않았습니다. 

그래서 또 구글링... 후 알게 된 이 문제의 풀이법

 

1-1. 정수 1을 만들 수 있는 경우의 수

- 0+1 = 1 

0에 1 하나만 더하면 되니까 1가지

 

1-2. 정수 2를 만들 수 있는 경우의 수

- 1+1 = 2

- 0+2 = 2

2가지

 

1-3. 정수 3을 만들 수 있는 경우의 수

- 1+1+1 = 3

- 1+2 = 3

- 2+1 = 3

- 0+3 = 4

4가지

 

2. 보기로 주어진 4를 만드는 경우는

1에 3을 더하는 경우, 2에 2를 더한 경우, 3에 1을 더한 경우의 수를 모두 더해주면 됩니다. 

5는 2에 3을 더한 경우, 3에 2를 더한 경우, 4에 1을 더한 경우의 수를 모두 더해주면 됩니다. 

그러면 다음과 같은 점화식을 도출할 수 있습니다. 

주어진 정수가 i라면 

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

 

i가 1, 2, 3인 경우만 기저조건으로 설정해 준 다음 10 이하 양수들의 경우의 수를 각각 구해서 배열에 저장한 뒤

테스트 케이스의 입력대로 출력해주면 됩니다. 

 

DP 문제를 풀며 느낀 건 점화식을 잘 도출하는 것이 굉장히 중요하구나...(아직 잘 못 함 ㅠ)

 

 

코드

 

#include <iostream>
#include <vector>

using namespace std;

const int MAX = 11;
int main(int argc, const char * argv[])
{
    int T;
    cin >> T;
    
    vector<int> ways(MAX, 0);
    ways[1] = 1; //1, 2, 3 기저조건 설정 
    ways[2] = 2;
    ways[3] = 4;
    //숫자가 몇 개 안되니까 미리 경우의 수를 모두 세팅해 놓음 
    for (int i = 4; MAX >= i; i++)
        ways[i] = ways[i-1] + ways[i-2] + ways[i-3];
    
    for (int i = 0; T > i; i++)
    {
        int n;
        cin >> n;
        cout << ways[n] << endl;
    }
    
    return 0;
}