[BaekJoon 9095번] 1, 2, 3 더하기(C++)

※주의※

저의 풀이가 정답은 아닙니다.

다른 코드가 더 효율적이거나 좋을 수 있습니다.

언제나 다른 사람의 코드는 참고만 하시기 바랍니다.

 

 

[문제 풀이 사이트]

 

 

9095번: 1, 2, 3 더하기

 

 

[문제 설명]

 

 

정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 7가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다.

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

정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오.

 

 

[입력]

 

 

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 정수 n이 주어진다. n은 양수이며 11보다 작다.

 

 

[출력]

 

 

각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다.

 

 

[입출력 예]

 

 

입력	출력
3 4 7 10	7 44 274

 

 

[문제 풀이]

 

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

내 풀이법을 정리해보도록 하겠다.

 

1. 테이블 정의하기

문제에 대한 테이블을 정의한다.(구하고자 하는 것)

dp[n] = n을 1, 2, 3의 합으로 나타내는 방법의 수(합을 나타낼때 수를 1개 이상 사용)

 

2. 점화식 찾기

테이블을 세웠으니 점화식을 찾아야한다.

 

우선 n의 값이 1 ~ 4까지 1, 2, 3 합으로 나타낼 수 있는 방법의 수를 표에 적었다.

1	2	3	4
1	1 + 1 2	1 + 1 + 1 2 + 1 1 + 2 3	1 + 1 + 1 + 1 2 + 1 + 1 1 + 2 + 1 3 + 1 1 + 1 + 2 2 + 2 1 + 3

 

n이 4일 때를 보면 아래와 같이

1 + 1 + 1 + 1 , 2 + 1 + 1, 1 + 2 + 1, 3 + 1

1 + 1 + 2, 2 + 2

1 + 3

방법의 수가 나온다.

 

표를 자세히 보면 아래와 같은 규칙을 찾을 수 있다.

n이 4일 때

(1 + 1 + 1) + 1 , (2 + 1) + 1, (1 + 2) + 1, (3) + 1

➔ 3을 1, 2, 3 합으로 나타내는 방법에 1을 붙임

 

(1 + 1) + 2, (2) + 2

➔ 2를 1, 2, 3 합으로 나타내는 방법에 2를 붙임

 

1 + 3

➔ 1을 1, 2, 3 합으로 나타내는 방법에 3을 붙임

 

그래서 위 내용을 기반으로

점화식 dp[n] = dp[n-1] + dp[n-2] + dp[n-3] 를 세울 수 있다.

 

내가 세운 점화식이 맞는지 n 이 5일 때도 1, 2, 3 합으로 나타낼 수 있는 방법의 수를 적어보았다.

n = 5일 때

5

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

4를 1, 2, 3 합으로 나타내는 방법에 1을 붙임(빨간색)

3을 1, 2, 3 합으로 나타내는 방법에 2을 붙임(파란색)

2를 1, 2, 3 합으로 나타내는 방법에 3을 붙임(초록색)

 

그리고 마지막으로 초기값을 정해야한다.

다이나믹 프로그래밍 문제를 풀 때 꼭 필요한 부분이다.

이 문제의 경우 세워진 점화식으로 보아 초기값은 최소 3개가 주어져야 한다.

그래서 초기값은

• n = 1일 때 1
• n = 2일 때 2
• n = 3일 때 4

로 정할 수 있다.

 

 

[최종 코드]

 

 

[GitHub]

 

 

GitHub - SmallPeanutPark/BAEKJOON: Study BaekJoon for Coding Test

 

 

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

int dp[12];

int plusNumber(int n) {
    if(dp[n] != -1) return dp[n];

    return dp[n] = plusNumber(n - 1) + plusNumber(n - 2) + plusNumber(n - 3);
}

int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);
    fill(dp, dp + 12, -1);
    dp[1] = 1;
    dp[2] = 2;
    dp[3] = 4;
    int TC;
    cin >> TC;
    for(int i = 0; i < TC; ++i) {
        int number;
        cin >> number;
        cout << plusNumber(number) << '\n';
    }
    return 0;
}