[백준 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의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오.

• 예시
  • 입력 : 3 4 7 10
  • 출력 : 7 44 274

풀이

직접 다 일일이 손으로 써가면서 만들어봐야 함. 그래서 규칙을 찾고 점화식으로 만들어서 풀면 됨. 내가 찾은 점화식은 f(n) = f(n-1) + f(n-2) + f(n-3) 이었음.

코드

#include <iostream>
#include <algorithm>

using namespace std;

int cache[11];

int main() {
    int T, n;
    cin >> T;

    cache[1] = 1;
    cache[2] = 2;
    cache[3] = 4;
    cache[4] = 7;

    for(int t = 0; t < T; t++) {
        cin >> n;

        for(int i = 5; i <= n; i++) {
            cache[i] = cache[i-1] + cache[i-2] + cache[i-3];
        }
        cout << cache[n] << endl;
    }

    return 0;
}