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

문제링크 : https://www.acmicpc.net/problem/5557

5557번: 1학년

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MAX = 987654321;

int N;
int arr[101];
ll dp [101][21]; //i번째 숫자까지의 조합으로 j를 만드는 경우
int main()
{
    ios_base::sync_with_stdio(0); 
	cin.tie(0);

    cin >> N;
    for(int i=0; i<N; i++)
    {
        cin >> arr[i];
    }

    dp[0][arr[0]] = 1; //초기화 (가장 처음 수는 무조건 들어감)

    for(int i=1; i<N-1; i++)
    {
        for(int j=0; j<21; j++)
        {
            if(!dp[i-1][j]) continue; //직전값이 없으면 패스
            if(j+arr[i]<21) dp[i][j+arr[i]] += dp[i-1][j]; //20이하인가?
            if(j-arr[i]>-1) dp[i][j-arr[i]] += dp[i-1][j]; //0이상인가?
        }
    }

    cout << dp[N-2][arr[N-1]];
    return 0;
}

처음에 문제를 잘못 이해하여 다소 헤맸던 dp 문제이다.

먼저 dp[i][j]은 i번째 숫자까지의 조합으로 j를 만드는 경우이다.

가장 처음 수는 무조건 들어가기에 dp[i][arr[i]]=1로 초기화를 하고 시작한다.

 

이후 이중 반복문을 돌리는데 i 반복문에서 맨 끝 숫자는 탐색을 할 필요가 없는 수이기에 N-1까지 탐색을 한다

이중반복문 안쪽에서 dp[i-1][j]의 유무를 판별하고 직전값이 있다면 이어서 탐색을 해주고 없다면 패스한다.

해당 j에 대해 arr[i]와 더해서 20이하인지 판별하고 20이하가 맞다면 dp[i][j+arr[i]]에 직전 dp값을 더해준다.

이어서 해당 j에 대해 arr[i]를 빼서 0이상인지 판별하고 0이상이 맞다면 dp[i][j-arr[i]]에 직전 dp값을 더해준다.

 

그리고 출력시에 dp[N-2][arr[N-1]]을 출력하는데 이는 위 반복문에서 i<N-1까지 탐색을 했기에 i=N-2이고,

arr[N-1]이 우리가 만들고자 하는 수(j)이기 때문이다.