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

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

9095번: 1, 2, 3 더하기

www.youtube.com/watch?v=R9WCxrPs2b8

규칙을 찾아내면 무척 간단한 문제다. 

물론 나는 다이나믹 프로그래밍을 이제야 공부하기 시작해서 나에겐 쉽지 않은 문제였다.

우선 규칙을 찾으려는 방향성은 올바르게 갔다. 

 

이 문제는 n 값이 11로 제한되어있어 메모제이션 방식을 사용하지 않고 재귀를 통한 완전탐색으로도 충분히 풀리는 문제이다.

 

너무 대충 끄적거린거라 좀 부끄러운데 

뭐 대략 설명해보자면 

우선 1,2,3 까지의 수는 미리 구해놔야한다. ex) 1 = 1 , 2 = 2, 3 = 4

그리고 4를 만드는 가장 큰 경우의 수들 먼저 살펴본다면

1.  3 + 1 

2. 2 + 2

3. 1 + 3

 

3 + 1 에서 3을 만들 수 있는 경우의수는 4개라고 이미 알고있다. 

2 + 2 에서 2를 만들 수 있는 경우의 수는 2개 

1 + 3 에서 1 을 만드는 경우의 수는 1개  

즉 4 + 2 + 1 = 7 이다. 

 

5 또한 이런 방식으로 구할 수 있다. 

#include <iostream>
#include <vector>
#include <string>

using namespace std;

int ret =0;

int solve(int n)
{
    if(n==1)
    return 1;
    if(n==2)
    return 2;
    if(n==3)
    return 4;

    return solve(n-1)+solve(n-2)+solve(n-3);
}

int main()
{
    int cnt,v=0;
    cin>>cnt;
    int*arr = new int[cnt];
    for(int i=0; i<cnt; i++)
    {
        cin>>v;
        arr[i] = solve(v);
    }
    for(int i=0; i<cnt; i++)
        cout<<arr[i]<<endl;
    
}

재귀를 통해 구현하였다.