백준 1495번 <기타리스트>

백준 알고리즘 1495번

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

1495번: 기타리스트

---

1495번

시작 볼륨과 볼륨 리스트 V가 주어졌을 때, 볼륨 리스트에서 마지막 곡을 연주할 수 있는 볼륨 중 최댓값을 구해라.

현재 볼륨이 P이고 지금 i번째 곡을 연주하기 전이라면, i번 곡은 P + V[i}거나 P - V[i]로 연주해야 한다.

 

입력으로 첫 줄에 곡의 개수 N, 시작 볼륨 S, 최대 볼륨 M이 주어지고 둘째 줄에는 볼륨 리스트 V가 주어진다.

 

출력은 마지막 곡을 연주할 수 있는 최대 볼륨을 출력하면 된다.

---

문제 해결

이 문제는 다이나믹 프로그래밍으로 해결할 수 있다.

 

시작 볼륨을 result 배열에 저장한다.

result 배열에 있는 값으로 현재 곡의 가능한 볼륨 값을 temp 배열에 넣고 모두 구한 다음에는 result 배열을 temp 배열로 바꾼다.

다시 result 배열에 있는 값으로 다음 곡의 가능한 볼륨 값을 구하는 식으로 정답을 구할 수 있다.

---

코드

def main():
    n, s, m = map(int, input().split())

    music = list(map(int, input().split()))

    result = [s]
    for i in range(n):
        temp = []
        for old in result:
            plus = old + music[i]
            minus = old - music[i]
            if plus <= m:
                temp.append(plus)
            if minus >= 0:
                temp.append(minus)
        temp = set(temp)
        result = temp
    if len(result) == 0:
        print(-1)
    else:
        print(max(result))
main()

---

결과

---