[Algorithm]Baekjoon 5557번 : 1학년

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

5557번: 1학년

 
int n;
int arr[101] = { 0 };
long long dp[101][21] = { 0 };
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> n;
 
    for (int i = 1; i <= n; ++i)
    {
        cin >> arr[i];
    }
 
    dp[1][arr[1]] = 1;
 
    for (int i = 2; i <= n - 1; ++i)
    {
        int curNum = arr[i];
 
        for (int j = 0; j <= 20; ++j)
        {
            if (j >= curNum)
            {
                dp[i][j - curNum] += dp[i - 1][j];
            }
 
            if (curNum + j <= 20)
            {
                dp[i][curNum + j] += dp[i - 1][j];
            }
        }
    }
 
    // dp[i][j] = > i번째 까지의 숫자로 j를 만들 수 있는 경우의 수.
 
    cout << dp[n - 1][arr[n]];
}
 

 

감을 못잡아서 다른분의 풀이를 참고했다.

길게 설명할것 없이, 이 문제의 점화식은 다음과 같다.

dp[i][j] = k 일 대, i번째 숫자까지를 이용해서 j를 만들 수 있는 경우의수는 k가지이다..