[BOJ9095 C++] 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 문제

DP는 이전 스텝에서 계산했던 것들을 바탕으로 다음 스텝으로 끌고오면서 계산하는 것이 중요 (한것같음)
그냥 문제를 보았을 때는,
아니 그러면 테스트 입출력에 입력이 7이면 출력이 44가 나오는데.
1 + 1 + 1 + 1 + 1 + 1 + 1
2 + 1 + 1 + 1 + 1 + 1
1+ 2 + 1 + 1 + 1 + 1
....
이걸 어떻게 세지? 라고 생각할 수 있지만,

우리가 푸는 데 있어 익숙했던 방식으로 바꿔서 생각하는 것도 중요.

결국 이 문제는 저렇게 나타나 있지만

다르게 말하면, 한번에 1, 2, 3칸만 갈 수 있을 때, N칸 위의 계단에 올라가는 방법을 세는 것과 똑같다.

1칸 -> 1칸 -> 1칸 -> .. 해서 4칸을 올라가는 방법
2칸 -> 1칸 -> 1칸 -> .. 해서 올라가는 방법

학부 수업때 그림도 그러면서 열심히 했었을 것임

예시를 들어서 4를 1, 2, 3의 더하기로 표현하는 방법 (입출력 예시에 있음) 은 7가지의 경우가 있다고 하는데
1+1+1+1
2+1+1
1+2+1
1+1+2
2+2
3+1
1+3
해서 7가지다.

사실 이거는 이 그림과 같음

0단에서부터 시작한다고 하고, 4단으로 올라가야 하는 경우 + 한번에 1, 2, 3 칸을 움직일 수 있다

맨처음 0단에서 1단으로 올라가는 경우의 수
-> 1칸 움직여서 1단으로 가는 방법 1가지

2단으로 올라가는 경우의 수
-> 0단에서 2칸 뛰어서 2단으로 이동
-> 1단에서 1칸 뛰어서 2단으로 이동 (1단으로 움직였던 과거의 내용. 이 그대로 올라간다 (DP!!))

3단으로 올라가는 경우의 수
-> 0단에서 3칸 뛰어서 3단으로 이동
-> 1단에서 2칸 뛰어서 3단으로 이동 (1단으로 움직였던 경우의 수가 그대로)
-> 2단에서 1칸 뛰어서 3단으로 이동 (2단으로 움직였던 경우의 수가 그대로!)
결국 식으로 하면 F(3) = F(0) + F(1) + F(2)

4단으로 올라가는 경우의 수
-> 0단에서는 4칸을 뛸 수 없음
-> 1단에서 3칸 뛰어서 4단으로 이동
-> 2단에서 2칸 뛰어서 4단으로 이동
-> 3단에서 1칸 뛰어서 4단으로 이동
F(4) = F(1) + F(2) + F(3)

이렇게 해서 앞으로 구해야 할 N 이전에, N-1, N-2, N-3에 대한 결과를 구해놨으니,
차례차례 끌고와서 사용하면 짠하고 나온다.

코드 구현은 이렇게 했음 (사실 recursive fuction으로 짜면 더 멋짐)

//
// Created by 신성준 on 2023/03/05.
//

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int T;
    cin >> T;
    for(int i = 1; i <=T; i++){
        int Num;
        cin >> Num;
        int arr[11];
        for(int n = 1; n <= Num; n++){
            if(n == 1){
                arr[n] = 1;
            }
            else if(n==2){
                arr[n] = 1 + arr[n-1];
            }
            else if(n ==3){
                arr[n] = 1+arr[n-1] + arr[n-2];
            }
            else{
                arr[n] = arr[n-1] + arr[n-2] + arr[n-3];
            }
        }
        cout << arr[Num] << endl;
    }
}

처음 1, 2, 3은 F(N) = F(N-1) + F(N-2) + F(N-3) 을 할 수가 없기 때문에 ..
if 로 처리를 하고, 4이상의 수는 else로 들어가서 위의 식을 따른다.