1495

백준 1495번

Link: 1495번: 기타리스트

---

문제 설명

무난하게 풀어냈던 DP 문제.

앞에서 풀어봤던 1학년 문제에서 썼던 알고리즘으로 풀면 쉽게 풀리는 문제였다.

오히려 이 문제가 좀 더 쉬웠던게, 이 문제에서 중요한 것은 횟수가 아닌 방문 가능 여부만 True/False로 확인하면 되기 때문이다.

1학년 문제 풀듯이 DP배열을 채우고 DP 배열에서 값이 true인 것의 최대 인덱스를 출력해주면 풀린다.

1학년 문제가 하나의 DP문제 풀이 템플릿이 되는 느낌이다.

잘 기억해둬야지

---

정답 코드

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

#include <iostream>

using namespace std;

bool DP[101][1001];

int N, S, M;

int main(){
    cin >> N >> S >> M;

    DP[0][S] = true;

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

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

                if(j + gap <= M){
                    DP[i][j+gap] = true;
                }
            }
        }
    }

    int result = -1;
    for(int i=0; i<=M; i++){
        if(DP[N][i]){
            result = i;
        }
    }

    cout << result << '\n';

    return 0;
}

---