BOJ 15989 - 1, 2, 3 더하기 4

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

 

어떻게 풀어야 할지 굉장히 고민을 많이 했던 문제.

처음엔 완전탐색, 백트래킹으로 풀려고 했었고 그럼 중복처리 ((1+1+2, 1+2+1)을 같은걸로 처리해야함.)

를 어떻게 처리해야 하나 고민하다가 배열을 3차원으로 만들어서 쓴 숫자들을 중복처리해줘야 하나도 고민을 해줬지만, 

그렇게 한다면 메모리를 너무 많이 차지해서 안됬다.

이런저런 고민을 하다가 결국 다른분들이 푼 방법을 봤는데, 생각보다 너무 간단했다.

냅색 문제 풀듯이 푸는데, 이게 보통 냅색문제가 숫자 몇을 만드려고 하는데 이때 최소 동전 몇개를 써야하냐 이런식인 경우가 많았던 것 같은데, 

이 문제는 그게 아니라 숫자 몇을 만드는데 경우의 수가 몇개가 필요하냐 뭐 이런식이었다.

그래서 보통?은 dp를 전부 inf로 채우고, dp[0] = 0; 으로 만든 다음 디피를 만들어가는 경우가 많았는데,

이문제같은경우 경우의 수기 때문에(방법을 알아내는 게 아니라) 아래와 같이 dp[0] = 1로 잡아주고 풀었다.

설명이 좀 이상하긴 한데, 코드로 보면 이해하기 편하다.

#include <bits/stdc++.h>
using namespace std;
int t;
int n;

int dp[10004];

int main()
{
    dp[0] = 1;
    for (int i = 1; i <= 3; i++)
    {
        for (int j = i; j <= 10000; j++)
        {
            dp[j] += dp[j - i];
        }
    }

    cin >> t;
    while (t--)
    {
        cin >> n;
        cout << dp[n] << "\n";
    }
    return 0;
}