[백준/c++] 9095번: 1, 2, 3 더하기

 

 

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

9095번: 1, 2, 3 더하기

 

문제 요약

 

정수 n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하자.

 

 

---

 

 

문제를 읽어보면 짧은 문제인데, 막상 풀려고 하면 막막해진다. 

우선 규칙을 찾아보도록 해보자.

 

문제는 주어진 n에 대해서 n을 1, 2, 3의 합으로 표현되는 경우의 수를 구하는 것인데, 작은 문제들을 먼저 해결하는 방식으로 생각해보면 i(≤n)를 1, 2, 3의 합으로 표현할 수 있는 경우의 수들을 찾으면 간단하게 풀 수 있을 것 같다.

 

X를 1, 2, 3의 합으로 표현하려면 그 전의 값(X-1)에 +1만 하면 X가 된다.

또한 (X-2)에 +2, (X-3)에 +3 하는 경우의 수의 합으로 표현할 수 있다.

 

(X-1의 1, 2, 3의 합으로 표현된 경우의 수) + (X-2의 1, 2, 3의 합으로 표현된 경우의 수) + (X-3의 1, 2, 3의 합으로 표현된 경우의 수)

여기서 X-4 이상은 나오면 안 된다. 1, 2, 3으로만 합할 수 있기 때문에^^

 

#include <iostream>
#define NUM 15
using namespace std;
int Dy[NUM];

void solution(){
    Dy[1] = 1; Dy[2] = 2; Dy[3] = 4;
    
    for(int i=4; i<=11; i++){
        Dy[i] = Dy[i-1] + Dy[i-2] + Dy[i-3];
    }
}

int main(){
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int t, n;
    solution();
    cin >> t;
    while(t--){
        cin >> n;
        cout << Dy[n] << '\n';
    }
    return 0;
}

 

 

 

 

 

💡공부 및 기록용 블로그이므로 오류가 있을 수 있습니다.💡

만약 문제에 오류나 오타가 있다면 댓글로 알려주세요➿
언제나 환영합니다. 감사합니다. 화이팅!