[DP][C++] 백준 9095번 : 1,2,3 더하기

문제

문제 링크

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

 

참고 블로그

https://wookeee.tistory.com/entry/CDP-%EB%B0%B1%EC%A4%80-9095%EB%B2%88-1-2-3-%EB%8D%94%ED%95%98%EA%B8%B0

[C++][DP] 백준 9095번 : 1, 2, 3 더하기

 

 

풀지 못한 이유

 문제를 보고 난 후 DP를 이용하여 풀면 되겠다는 것은 쉽게 떠올릴 수 있었다. 하지만 점화식이 떠오르지 않아서 어쩌면 굉장히 허무하게 1시간 정도를 소모하였다. 개인적으로, 최대 1시간까지 생각해보고 방법이 떠오르지 않는다면 답지를 본다. 그래서 위의 블로그를 통해 점화식이 어떻게 나오는지를 알 수 있었다. 

 

  이번 문제 역시 문제를 간단하게 보려고 하지 않고(= 단순하게 만드려고 하지 않고) 오히려 복잡하게 생각해서 풀지 못한 것 같다. 

  문제를 단순하게 보기 위해 노력해야겠다.

 

코드

 점화식을 이해하고 난 후 내가 구현한 코드이다.

 문제에서 최대 11까지의 수에 대한 답만 출력하면 되었기 때문에, 1~11 까지 숫자를 표현할 수 있는 방법의 수를 미리 구해 놓고, 들어오는 입력에 따른 결과만을 바로 출력할 수 있도록 구현하였다.

#include <iostream>

using namespace std;
int t; // 테스트 케이스 개수
int n; // 주어진 정수
int wqy; // 가능한 방법
int dp[12];

int main()
{
    // dp 초기화
    dp[0] = 0; dp[1] = 1; dp[2] = 2; dp[3] = 4;
    // 점화식 이용
    for(int i= 4; i<12; i++){
        dp[i] = dp[i-3] + dp[i-2] + dp[i-1];
    }
    
    cin >> t;
    for(int i=0; i<t; i++){
        cin >> n;
        cout << dp[n] << "\n";
    }
    

    return 0;
}

 

 

메모!

어떻게 풀어야 할 지 잘 감이 오지 않을 때에는 최대한 단순하게 문제를 바꿔보려고 하기!

특히 점화식이 잘 떠오르지 않을 때에는, 주어져 있는 예시를 만들어내려고 하지 말고 문자로 대입해보기!