[백준 5557] 1학년 (C++)

문제

백준 5557

5557번: 1학년

풀이

점화식이 은근 간단한데 구현에 시간이 오래걸렸습니다.

dp[i][j]는 i+1번째 차례에 +, - 연산으로 숫자 j를 만들 수 있는 경우의 수를 뜻합니다.

dp[0][num[0]] 부터 시작하므로 1을 넣어줍니다.

그 후 루프를 돌면서 dp[i-1][j]값이 0보다 클 경우(가는 방법이 존재할 경우)

더한 값과 뺀 값을 비교하여 조건(0이상 20이하)을 만족한다면 dp에 저장합니다.

루프가 끝난 뒤 num[N-1] 값이 나오는 경우의 수를 dp배열의 값으로 출력해줍니다.

소스 코드

#include<iostream>
#include<vector>
using namespace std;
 
int N;
int num[100];
long long dp[100][21];
int main()
{
    cin >> N;
    for (int i = 0; i < N; i++)
    {
        cin >> num[i];
    }
    dp[0][num[0]] = 1;
    for (int i = 1; i < N - 1; i++)
    {
        for (int j = 0; j < 21; j++)
        {
            if (dp[i-1][j] > 0)
            {
                int add = j + num[i];
                int sub = j - num[i];
                if (add < 21)
                    dp[i][add] += dp[i - 1][j];
                if (sub >= 0)
                    dp[i][sub] += dp[i - 1][j];
            }
        }
    }
    cout << dp[N - 2][num[N - 1]];
    return 0;
}