[python] 백준 - 1495. 기타리스트

🤔문제 해결

1. S1 | 다이나믹프로그래밍

2. 각각의 연주 차례에 가능한 볼륨을 저장하기 위해 2차원 리스트를 만든다.

3. 리스트를 설명하자면 맨 첫줄(i = 0)은 연주 시작전 단계이고 값이 0이 아니라 1인 부분은 내가 가지고 있는 볼륨이다. 현재 테스트케이스 예시(S=5)로 작성됐으므로 [0][5] = 1 이다.

4. 테스트케이스: 시작값 5, 최대값 10, 연주리스트 = [5, 3, 7]

5. 첫번째 연주를 하기 전에 볼륨을 바꾼다. 현재 볼륨은 5, 첫번째 연주 볼륨은 5 이므로 5+5 = 10, 5-5 = 0 으로 둘다 0보다 크고 10보다 작으므로 아래와 같이 저장할 수 있다.

6. 첫번째 연주를 하기 전에 볼륨을 바꾼다. 첫번째와 다른점은 현재 볼륨이 2가지(0과 10)이다. 먼저 현재 볼륨은 0, 두번째 볼륨은 3 이므로 0+3 = 3, 0-3 = -3 으로 3만 선택할 수 있다. 다음 현재 볼륨은 10, 두번째 볼륨은 3 이므로 10+3 = 13, 10-3 = 7 으로 7만 선택할 수 있다.

7. 이렇게 하다보면 마지막에는 아래와 같이 나오게 되고 마지막 행에서 값이 1인 가장 큰 인덱스를 선택하여 출력한다.
만약 값이 1인 부분이 없다면 -1(마지막 연주를 못할 경우)를 출력한다.

 

💨 다이나믹 프로그래밍은 항상 어렵다. 먼저 재귀로 풀어봤더니 역시 시간초과가 발생했다. 

 

💻소스 코드

def volume():
    for i in range(1, N + 1):
        for j in range(M + 1):
            # print(i, j)
            # 현재 가지고 있는 볼륨(값이 1인 경우)에서만 시작할 수 있다!
            if dp[i - 1][j] == 0:
                continue
            # 볼륨을 올리는 경우
            if j + V[i - 1] <= M:
                dp[i][j + V[i - 1]] = 1
            # 볼륨을 내리는 경우
            if j - V[i - 1] >= 0:
                dp[i][j - V[i - 1]] = 1

            # for row in dp:
            #     print(row)
            # print()


def answer():
    # 마지막줄에 볼륨(값이1) 이 있어야 연주가 가능한 것!!! 아니면 -1을 출력
    for i in range(M, -1, -1):
        if dp[-1][i] == 1:
            print(i)
            return
    else:
        print(-1)


if __name__ == "__main__":
    N, S, M = map(int, input().split())
    V = list(map(int, input().split()))
    # 최대볼륨(M)까지 각 노래마다 가능한 볼륨 저장
    dp = [[0] * (M + 1) for _ in range(N + 1)]
    # 0번째 행은 노래 시작전
    # 1번째 행부터 첫 노래 시작
    dp[0][S] = 1

    # 가능한 볼륨 저장 하기
    volume()
    # 마지막 연주 때의 가장 큰 볼륨
    answer()

 

📕문제 확인

출처: BACKJOON ONLINE JUDGE

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

1495번: 기타리스트

---

---

---

문제

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

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

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

입력

첫째 줄에 N, S, M이 주어진다. (1 ≤ N ≤ 100, 1 ≤ M ≤ 1000, 0 ≤ S ≤ M) 둘째 줄에는 각 곡이 시작하기 전에 줄 수 있는 볼륨의 차이가 주어진다. 이 값은 1보다 크거나 같고, M보다 작거나 같다.

출력

첫째 줄에 가능한 마지막 곡의 볼륨 중 최댓값을 출력한다. 만약 마지막 곡을 연주할 수 없다면 (중간에 볼륨 조절을 할 수 없다면) -1을 출력한다.