[DP (동적 프로그래밍) / BOJ 15989 / C++] 1,2,3 더하기 4

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

15989번: 1, 2, 3 더하기 4

 

오랜만에 올린다 ㅠ 블로그에 글 열심히 써야겠다.

 

DP가 너무 어려워서 천천히 해가는 중이다.. DP는 브루트포스, 백트래킹 안되면 해야하는 친구이다.

 

이 문제는 3중 for문 돌려서 푸는 문제는 아닌건 알것이다. 그렇다면 어떻게 해결해야할까??

 

논리가 생각하기 어렵다,, 바로 해결 방법을 봐보자.

먼저 간단하게 살펴보자면, 최종적인 dp배열을 무엇으로 정의해야하는지 생각해야한다. dp[3]이라 함은, 1,2,3으로 가능한 경우의 수를 의미한다.

 

 

먼저 1로 가능한 경우의수만 봐보자. dp[0]부터 시작해서 모두 1가지 경우의 수라는 것은 직관적일 것이다.

(이때의 dp 배열의 의미는, 1로 가능한 경우의 수를 말한다.)

 

1,2로 가능한 경우의 수를 봐보자. 일단 '2'라는 값을 만들려면, 0에서 2를 더하면된다. 즉, '0'을 만드는 경우의 수를 '2'를 만드는 경우의 수에 덧붙여주면 된다는 의미이다.

(이때의 dp배열의 의미는, 1,2로 가능한 경우의 수를 말한다.)

 

마찬가지로, '4'라는 값은 '2'에서 2를 더하면 된다. 즉, '2'를 만드는 경우의 수를 '4'를 만드는 경우의 수에 덧붙여주면 된다.

이때, '2'를 만드는 경우의 수는 '0'을 만드는 경우의 수를 이미 포함하고 있다는 점을 생각하자!!

 

이러한 논리를 코드로 표현하자면,  아래와 같이 생각해볼 수 있다!!

 

 

#include <bits/stdc++.h>

using namespace std;

int dp[10001], t;

int main(){
    
    
    dp[0] = 1;
    
    for(int i = 1; i <= 3 ; i++){
        for(int j = 1 ; j < 10001 ; j++){
            if(j-i>=0) dp[j] += dp[j-i];
        }
        
        
    }
    
    cin >> t;
    while(t--){
        int n=0;
        cin >> n;
        cout << dp[n] << '\n';
    }
    
}