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

1. 개요

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

9095번: 1, 2, 3 더하기

1-1. 설명

정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성한다. 예시는 위의 링크를 참조한다. 

1-2. 제한 사항

 - 첫 줄에 테스트 케이스의 개수 T가 주어지며, 후에 정수 n이 주어짐

 - n은 양수이며 11보다 작음

---

2. 구현

2-1. 풀이

다이나믹 프로그래밍을 이용한다. DP인 것을 인지했지만, 아직 미숙하여 점화식은 다른 분의 풀이를 보고 참고하였다. 풀이를 확인하고 싶다면 https://hyun-am-coding.tistory.com/entry/DP-DP-%EA%B0%84%EB%8B%A8%ED%95%9C-%EB%AC%B8%EC%A0%9C-%EB%B0%B1%EC%A4%80-1-2-3-%EB%8D%94%ED%95%98%EA%B8%B0-%ED%92%80%EA%B8%B0 여기서 확인이 가능하다. 

2-2. 코드 

#include <iostream>
using namespace std;

int dp[23];

int solution(int N);

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int T, N;
    cin >> T;
    dp[0] = 1, dp[1] = 2, dp[2] = 4;
    // 1을 더할 땐 1 하나만 존재하므로 dp[0] = 1
    // 2를 구할 때는 1+1, 2가 존재하니 dp[1] = 2
    // 3을 구할 때는 1+1+1, 1+2, 2+1, 3이므로 dp[2] = 4
    
    for (int i = 0; i < T; i++) {
        cin >> N;
        int result = solution(N);
        cout << result << "\n";
    }
    
    return 0;
}

int solution(int N) {
    for (int i = 3; i < N; i++) {
        dp[i] = dp[i - 3] + dp[i - 2] + dp[i - 1];
        // 점화식은 dp[n] = dp[n-3] + dp[n-2] + dp[n-1]
    }
    return dp[N-1];
}