백준 - 9095번: 1, 2, 3 더하기

 

---

 

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

9095번: 1, 2, 3 더하기

 

 이번 문제는 n이 주어졌을 때, 1, 2, 3만을 이용하여 n을 만들 수 있는 가지수를 구하는 문제이다. 그리고 주의할 점이 있는데, 만약 n이 4일 경우, 1 + 3과 3 + 1은 서로 다른 경우로 취급한다는 것이다. 이 점 때문에 처음에는 어떻게 접근해야 할지 도저히 감이 잡히지 않았다. 하지만 가만히 생각해보니 생각보다 쉬운 문제였다.

 예를 들어, n이 4일 경우, dp[4]를 생각해보자. 1, 2, 3만을 이용하여야 하기에 n - 1, n - 2, n - 3까지 고려해야 한다. 우선 3이다. 3에서 4를 만들기 위해서는 모든 3이 되는 식에서 1만 더해주면 된다. 1 + 1 + 1로 3을 만들었다면, 여기에 + 1만 해주면 되고 2 + 1로 3을 만들었어도 + 1만 해주면 된다. 이를 통해 dp[4] = dp[3] + ... 임을 알 수 있다. 

 이어서 2이다. 이 경우 역시, 모든 2가 되는 식에 2만 더해주면 된다. 1 + 1로 2를 만들었다면, + 2만 해주면 된다. 여기서 잠시 1 + 1로 2를 만든 후, 여기에 다시 + (1 + 1)을 해줄 수도 있지 않을까라 생각할 수도 있다. 하지만, 그런 케이서는 전부 dp[3](dp[n - 1])에 이미 포함이 되어 있기에 고려하지 않아도 된다. 마지막으로 1일 때도 마찬가지로 모든 1이 되는 식에 + 3만 해주면 된다. 이를 종합해 점화식을 구성하면 다음과 같다.

 

dp[n] = dp[n - 1] + dp[n - 2] + dp[n - 3]

 

#include <iostream>
#include <vector>
#define MAX 12

using namespace std;

int T, n;
int dp[MAX];
vector<int> answer;

int Check(int num)
{
    if (dp[num] > -1)
        return dp[num];
	
    // 점화식: dp[n] = dp[n - 1] + dp[n - 2] + dp[n - 3]
    return dp[num] = Check(num - 1) + Check(num - 2) + Check(num - 3);
}

int main()
{
    ios_base::sync_with_stdio(0);
	std::cout.tie(NULL);    
	std::cin.tie(NULL);
    
    for (int i = 0; i < MAX; ++i)
        dp[i] = -1;
    dp[1] = 1;
    dp[2] = 2;
    dp[3] = 4;

    cin >> T;

    while(T--)
    {
        cin >> n;

        int result = Check(n);

        answer.push_back(result);
    }

    for (int i = 0; i < answer.size(); ++i)
        cout << answer[i] << endl;
  

    return 0;
}