[Algorithm]Baekjoon 9095번 : 1,2,3 더하기

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

9095번: 1, 2, 3 더하기

int dpArray[1001];
 
int dp(int n)
{
    for (int i = 5; i <= n; i++)
    {
        dpArray[i] = dpArray[i - 1] + dpArray[i - 2] + dpArray[i - 3];
    }
 
    return dpArray[n];
}
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
 
    int num = 0;
    int temp = 0;
    vector<int> result;
    dpArray[0] = 0;
    dpArray[1] = 1;
    dpArray[2] = 2;
    dpArray[3] = 4;
    dpArray[4] = 7;
 
    cin >> num;
 
    for (int i = 0; i < num; i++)
    {
        cin >> temp;
        result.push_back(dp(temp));
    }
 
    for (auto temp : result)
    {
        cout << temp << endl;
    }
}

 

문제 자체는 실버3 정도로 어렵지 않다. 

이번 문제같은 경우는 일일이 경우의 수를 찾아서 규칙을 찾은게 아니라, 타일링문제 풀때 점화식도출방법을 응용해서 생각했더니 원하는 답이 나왔다. 

f(4)까지 일일이 경우의 수만 구하더라도, f(n) = f(n-1) + f(n-2) + f(n-3) 인 걸 알수있다.

하지만 그러다가 경우의 수가 너무 중구난방이라 규칙을 찾기 힘들수도 있으니, 좀 더 근본적으로 다가가서 풀어야한다.

 

 

 n이 4인 경우에, sum = 0부터 값을 하나씩 더해보기로 하자.

 

1을 먼저 더한다면, 남은값은 3, 즉 n-1이다.

2를 먼저 더한다면, 남은값은 2, 즉 n-2 이다.

3을 먼저 더한다면, 남은값은 1, 즉 n-3 이다.

 

이것도 타일링문제처럼, 왼쪽부터 뭔가 세워놓고 생각해보면 된다. 주어진 숫자(타일)을 먼저 세워놓고, 남은 숫자(공간)이 얼마나 체크해보면 된다.