백준: 1495 기타리스트

문제

1495번: 기타리스트

 

문제 풀이

 연주할 곡과 현재 볼륨, 최대 볼륨과 함께 각 곡을 연주할 수 볼륨 리스트가 주어진다. 조절할 수 있는 볼륨은 현재 연주곡이 1번이라면 볼륨 리스트 1번의 볼륨 크기만큼 추가하거나, 더하여 0보다 크거나 최대 볼륨보다는 작을 경우에만 연주가 가능하다. 만약 연주가 불가능하다 보면 -1을 출력하여야 한다.

 

 처음 문제를 접하였을 때는 연주할 수 있는 볼륨을 -하거나 +하여야 하므로, DFS로 풀어야 한다고 생각하였다. 하지만 DFS로 풀 경우 메모리 초과가 발생하여 통과하지 못한다. 따라서 DP를 통해 풀어야 해당 문제를 풀 수 있다. 이걸 DP로 어떻게 풀지 계속 고민하다가 다른 분들의 풀이를 참고하였다.

 

 풀이 방식은 다음과 같다.

• 리스트를 만들 때, list[연주하는 곡의 수][최대 볼륨]으로 2차원 배열을 만든다.
• list[0]은 아무것도 연주하지 않은 상태, 최초에 볼륨을 적용한 상태이므로 list[0][s] = True이다.
• 2중 반복문을 순회하면서 list[1], list[2] ... 로 접근하며 볼륨의 상태를 체크한다.
• n * m 만큼의 반복문을 순회하면, list[n]에 최대 볼륨을 체크한다.
  • 만약 list[n]에 체크된 볼륨이 없다면, 마지막 곡을 연주할 수 없는 것이다.
• 즉 위의 그림과 같이 트리를 순회하는 과정을 2차원 배열을 체크함으로써 가능하다. 이는 반복문의 순회만 필요한 작업이므로 N*M의 크기가 크지 않다면 DFS보다 효율적으로 탐색할 수 있다.

코드

from sys import stdin


if __name__ == "__main__":
    n, s, m = map(int, stdin.readline().split())
    v = list(map(int, stdin.readline().split()))

    answer = [[False for _ in range(m + 1)] for _ in range(n + 1)]
    answer[0][s] = True

    for play_song in range(1, n + 1):
        for volume in range(m + 1):
            if not answer[play_song - 1][volume]:
                continue
            next_volume = v[play_song - 1]
            if volume + next_volume <= m:
                answer[play_song][volume + next_volume] = True

            if volume - next_volume >= 0:
                answer[play_song][volume - next_volume] = True

    try:
        print(m - answer[-1][::-1].index(True))
    except:
        print(-1)