백준, BOJ, 9095번 C++ [CPP]

이 문제 또한.. DP로 즉, 이전 결과가 다음 결과에 쓰이는 문제라고 볼 수 있다.

 

추가 시간이 없다는 말은 언어마다 추가시간이 없다는 말 같다.

C++은 항상 기준이 되므로 시간제한에 추가시간이 있을까 없을까 고민안해도 된다.

시간 초과나면 잘못푼거다 ㅎ

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

9095번: 1, 2, 3 더하기

 

---

 

맞는 풀이

#include<iostream>

using namespace std;

int num[11];

int main(){
    int n;
    cin >> n;
    num[1] = 1;
    num[2] = 2;
    num[3] = 4;
    
    
    
    //왜 이렇게 되는가?
    // 4를 만드려면 3인 상태에서 1을 더하는 가짓 수, 2인 상태에서 2를 더하는 가짓수, 1인 상태에서 3을 더하는 가짓 수의 합이 필요하다.
    // 즉, 3인 상태에서 1을 더하는 가짓수 1, 2인 상태에서 2를 더하는 가짓 수 2, 1인 상태에서 3을 더하는 가짓수 4
    // 7이 만들어진다.
    // 5도 그렇다. 4인 상태에서 1을 더하는 가짓 수, 3인 상태에서 2를 더하는 ....
    // 즉, 주어진 숫자가 차례로 3개 (1,2,3)이 주어진다면 10 -> 7 + 3, 8 + 2, 9 + 1 // 7 -> 4 +3, 5 + 2, 6 + 1...
    // 과 같이 이전에 만들어진 숫자의 개수에 1을 더하느냐.. 2를 더하느냐.. 3을 더하느냐 차이일 뿐이다.
    for(int i = 4; i<11; i++){
        num[i] = num[i-1] + num[i-2] + num[i-3];
    }
    while(n--){
        int in;
        cin >> in;
        cout << num[in] << "\n";
    }
    
    
}

 

우선 설명을 다 써놓았다.

 

우선 이러한 문제를 풀 때 DP테이블을 만들어 저장하면서 풀라는 것인데..

이러한 문제가 어떤 것인지 살펴볼 필요가 있다.

 

사실 점화식이 나오기 마련인데..? 조금 헷갈릴 때가 있어서 하나씩 해보면 된다.

 

1을 만들 때 어떻게 만드나..?

...해보다보면

4를 만들 때 어떻게 만들까??? 이전 것을 이용할 수 있을까??? 라고 생각하는 순간

알게된다.

 

DP 문제는 거의 하다보면 나오는 것처럼 

고등학교 수학에서 수열과 다를 바가 없다.

수열을 보면서 규칙을 찾아내는 것 정도만 할 수 있다면

DP는 그냥 풀 수 있다는 말이다.