백준 1495번 기타리스트 [DP] :: 마이구미

이번 글은 백준 알고리즘 1495번 "기타리스트" 를 다뤄본다.

문제 해결은 동적계획법을 활용할 수 있다.

Day Of Mourning의 기타리스트 강토는 다가오는 공연에서 연주할 N개의 곡을 연주하고 있다. 지금까지 공연과는 다른 공연을 보여주기 위해서 이번 공연에서는 매번 곡이 시작하기 전에 볼륨을 바꾸고 연주하려고 한다.

먼저, 공연이 시작하기 전에 각각의 곡이 시작하기 전에 바꿀 수 있는 볼륨의 리스트를 만들었다. 이 리스트를 V라고 했을 때, V[i]는 i번째 곡을 연주하기 전에 바꿀 수 있는 볼륨을 의미한다. 항상 리스트에 적힌 차이로만 볼륨을 바꿀 수 있다. 즉, 현재 볼륨이 P이고 지금 i번째 곡을 연주하기 전이라면, i번 곡은 P+V[i]나 P-V[i] 로 연주해야 한다. 하지만, 0보다 작은 값으로 볼륨을 바꾸거나, M보다 큰 값으로 볼륨을 바꿀 수 없다.

곡의 개수 N과 시작 볼륨 S, 그리고 M이 주어졌을 때, 마지막 곡을 연주할 수 있는 볼륨 중 최대값을 구하는 프로그램을 작성하시오. 모든 곡은 리스트에 적힌 순서대로 연주해야 한다.

먼저 주어지는 문제에서 2가지 조건 캐치 해야한다.

1. 현재 볼륨 P는 i번째 곡을 연주하기 전, i번 곡은 P+V[i] 또는 P-V[i] 연주 가능하다.
2. 0보다 작은 값 그리고 M보다 큰 값은 볼륨으로 바꿀 수 없다.

2가지 조건만 이해한다면, 문제가 무엇을 원하는 지 알 수 있다.

이해가 안 갈 수 있으니 그림으로 표현해보면 아래와 같다.

주어지는 입력은 N = 3, S = 5, M = 10, 볼륨 리스트 = 5 3 7 으로 가정해보자.

0보다 작거나, M 값인 10보다 크면 안된다.

위와 같이 진행되기 때문에, 답은 10이 된다.

이 문제의 점화식은 위 그림을 보면서 생각하면 된다.

2번째 곡일 때 -3, 13 의 경우에는 조건에 맞지 않아 바꿀 수 없다.

곡이 들어날수록 경우의 수는 2제곱으로 늘어가지만, 사실상 바꿀 수 없는 경우는 계산을 할 필요가 없게 된다.

그렇기에, N번째 곡마다 +- 볼륨으로 바꿀 수 있는 지 체크를 하면 된다.

이것을 활용해 점화식을 도출하면 아래와 같다.

dp[N][S] = N번째 곡일 때, 볼륨 S 가능 여부

N번째 곡일 때, 볼륨 S의 가능 여부는 이전 곡(N-1번째)의 볼륨을 확인하여 N번째 곡에서 바꿀 수 있는 볼륨(V[N])을 +- 해주면 된다.

이 과정을 위에서 언급한 매번 2가지 조건을 충족시키면서 말이다.

코드를 보면 쉽게 이해할 수 있을 것이다.

dp[0][s] = true;

for (int i = 1; i <= n; i++) {

    for (int j = 0; j <= m; j++) {

        if (!dp[i - 1][j]) {
            continue;
        }

        if (j - array[i] >= 0) {
            dp[i][j - array[i]] = true;
        }

        if (j + array[i] <= m) {
            dp[i][j + array[i]] = true;
        }

    }

}

전체 소스는 아래 Github 링크를 참고하길 바란다.

백준 알고리즘 1495번 기타리스트 전체 소스

https://github.com/hotehrud/acmicpc/blob/master/dp/1495.java