5557

백준 5557번

Link: 5557번: 1학년

---

문제 설명

간만에 문제풀이.

예전에 풀다가 못풀었던 DP 문제다.

아이디어는 그리 대단치는 않은데, 이거 못떠올려서 주변에 물어봐가면서 풀었다.

맨 첫번째 숫자에 대해 DP[N]의 값을 1로 지정한 다음, 그 다음에 오는 인풋 숫자들을 하나씩 읽으며 DP배열을 채운다.

윗줄의 DP[i]의 값이 0이 아닌 경우에 대해 현재 읽은 인풋 숫자를 더하고 뺀 값을 인덱스로 하는 DP 값을 윗줄의 값만큼 더해준다.

모든 인풋값에 대해 수행한 다음, 마지막으로 들어오는 값의 DP배열 값을 출력해주면 정답이다.

DP문제가 다 그렇듯이 아이디어만 제대로 떠올리면 쉽게 풀리는 문제.

1차원 배열로 푸는 DP문제는 그래도 좀 풀만한것 같은데, 이런 2차원 배열로 푸는 DP는 아직 어려운것 같다.

앞으로 시험 대비해서 이런 DP도 제대로 풀 수 있을때까지 연습해야겠다.

이제 다시 매일 문제풀이후에 올릴 예정.

---

정답 코드

//
// Created by Keith_Lee on 22/03/2019.
//

#include <iostream>

using namespace std;

long long DP[101][21] = {0, };

int main(){
    int N;

    cin >> N;

    int start;
    cin >> start;

    DP[0][start] = 1;

    for(int i=1; i<N-1; i++){
        int nextNum;
        cin >> nextNum;

        for(int j=0; j<=20; j++){
            if(DP[i-1][j] > 0){
                if(j - nextNum >= 0){
                    DP[i][j-nextNum] += DP[i-1][j];
                }
                if(j + nextNum <= 20){
                    DP[i][j+nextNum] += DP[i-1][j];
                }
            }
        }
    }

    int resultNum;
    cin >> resultNum;

    cout << DP[N-2][resultNum] << '\n';

    return 0;
}

---