백준, BOJ, 1495번, 기타리스트 : C++ [CPP]

이전의 1학년 문제와 같다.

다만 경우의 수를 고려하는 것이 아닌

그냥 최댓값이 무엇이냐?라는 것이다.

그래서 솔직히 BFS로 풀어볼까도 생각했었다. 결국 N번째 도착지만 알면 되니까..?

아무튼 근데 그냥 DP로 풀었다. 점화식이 조금 더 직관적이어서 그랬다.

 

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

 

---

 

#맞은 풀이

#include <iostream>
#include <algorithm>

using namespace std;

int N, S, M;

int arr[52];
int dp[52][1001];    //dp[i][j]는 i번째에 볼륨 j를 가질 수 있는지 여부(-1, 1);


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

    //N개의 곡 입력받음.(첫번째 곡은 주어졌고 N번의 볼륨을 변화시켜야함
    //총 N+1개의 곡을 연주 (나는 0번째에 시작곡을 넣기로 함)
    for (int i = 1; i <= N; i++) {
        cin >> arr[i];
    }

    //dp테이블 초기화
    for (int i = 0; i <= N+1; i++) {
        fill(dp[i], dp[i] + (M + 1), -1); //dp 테이블 -1로 초기화
    }


    //시작 곡의 크기.
    dp[0][S] = 1; //처음엔 S의 볼륨 크기를 가지고 시작한다.

    //나머지 dp테이블
    for (int i = 1; i <= N; i++) {
        for (int j = 0; j <= M; j++) {
            //이전 곡에서 볼륨의 값을 j로 가질 수 있다면
            if (dp[i - 1][j] == 1) {

                //이전의 볼륨 값에서 현재 볼륨의 차이를 더하거나
                if (j + arr[i] <= M) {
                    dp[i][j + arr[i]] = 1;
                }
                //빼는 값도 가질 수 있는지 확인
                if (j - arr[i] >= 0) {
                    dp[i][j - arr[i]] = 1;
                }
            }
        }
    }

    int ans = -1;
    for (int j = 0; j <= M; j++) {

        //해당 볼륨을 가질 수 있으면 최댓값 갱신
        if (dp[N][j] == 1) {
            ans = max(ans, j);
        }
    }

    cout << ans;

    return 0;
}

 

DP를 풀다보면 느끼는 것이

항상 N이 주어지고 N번째의 무엇인가를 찾는다.

게다가 N이 엄청 크거나 N이 작지만 연산이 많이될 경우

항상 Memoization을 통해서 하위 답을 통해서 답을 찾아나간다.