백준 5557: 1학년

다이나믹을 사용하면 되는 문제 경우의 수가 오지게 많아서 long long 을 써줘야 한다. int 썻다가 피를 봤다.. 원리는 어렵지 않다. 점화식을 세우면 되는데

d[i번째 수를 사용][현재 수] 가 경우의 수를 나타낸다고 했을 때 입력받은 a배열에서 해당 만큼 빼주고 더해주면 된다. 

신기한 건 나는 답을 못찾겠을 때 구글에 백준 문제 번호를 검색하는데 내 코딩과 비슷한 사람이 보인다..

#include <iostream>
using namespace std;
int n;
long long d[103][21];
int a[103];
 
int main()
{
    cin >> n;
    for (int i = 0; i < n; ++i)
        cin >> a[i];
    d[0][a[0]] = 1;
    for (int i = 1;i <= n - 2; ++i)
    for (int j = 0; j <= 20; ++j)
    {
        if (d[i - 1][j])
        {
            if (j - a[i] >= 0)
                d[i][j - a[i]] += d[i - 1][j];
            if (j + a[i] <= 20)
                d[i][j + a[i]] += d[i - 1][j];
        }        
    }
    long long ans = d[n - 2][a[n - 1]];
    cout << ans << endl;
    return 0;
}