[GDSC Week4-1] 백준 9095번:: 1, 2, 3 더하기 (C++)

 

* 생각한 아이디어 및 문제 풀이

다이나믹 프로그래밍을 통해 문제를 푸는 방법은 1, 2, 3의 합을 미리 수동으로 구해놓아야 한다는 것이 시간을 아낀다는 점의 핵심이다.

1을 1, 2, 3의 합으로 만드는 방법 : 1가지(1)로 dp[1] = 1

2를 1, 2, 3의 합으로 만드는 방법 : 2가지(1+1, 2)로 dp[2] = 2

3을 1, 2, 3의 합으로 만드는 방법 : 4가지(1+2, 2+1, 1+1+1, 3)

그리고 +1된 다음수부터는 이렇게 1, 2, 3을 합한 방법에서 값을 +1씩 더하면 되는 것이므로

dp[i] = dp[i-1] + dp[i-2] + dp[i-3]의 공식으로 만들어지는 것을 알 수 있다.

 

* 코드

#include <iostream>
using namespace std;

int main(){
    ios_base::sync_with_stdio(false); 
    cin.tie(0); cout.tie(0);
    
    int T;
    cin >> T;
    
    int dp[11];
    dp[1] = 1;
    dp[2] = 2;
    dp[3] = 4;
    
    for(int i=4; i<11; i++){
        dp[i] = dp[i-1] + dp[i-2] + dp[i-3];
    }
    
    while(T--){
        int num;
        cin >> num;
        cout << dp[num] << '\n';
    }
    
}

 

* 회고

: 풀고 나서 정말 쉬운 문제라는 것을 알았는데...

이전까지 1, 2, 3의 초기화 된 값이 무엇인지 헤매다가 시간이 많이 걸렸다.

 

 

* 문제 링크 : https://www.acmicpc.net/problem/9095

9095번: 1, 2, 3 더하기

* 참고 코드 : https://hub1234.tistory.com/30

[백준 9095번]다이나믹 프로그래밍 1,2,3 더하기