[Python] 백준(BOJ): 1495 기타리스트

문제

1495번: 기타리스트

---

풀이

a.  접근법

https://www.acmicpc.net/problem/1463 문제와 유사하게 메모이제이션(memoization) 방식으로 접근하였다

DP[i] = i번째 곡을 연주할 때 가질 수 있는 볼륨값

P+V[i]와 P-V[i]가 범위 내의 볼륨 값을 가진다면 DP에 추가, DP[i]의 볼륨값을 가지고 DP[i+1]의 볼륨값을 구해낸다

이 때 마지막 곡을 연주할 수 없는 경우 (DP에 값이 없는 row가 존재하게 되는 경우엔 다음 곡에 대한 볼륨을 계산할 수 없어지므로,  더 이상의 볼륨 조절이 불가능하다)에 대한 예외처리를 수행한다

예제로 확인해보면 다음과 같다

1495 기타리스트

 

b.  풀이

추가적으로 중복된 값에 대하여 다시 메모이제이션을 수행하는 경우를 제거하기 위해 DP를 set으로 선언하고, 추가적으로 DP의 index를 i%2로 설정하여 메모리초과 해결. 최적화된 코드는 다음과 같다

n, s, m = map(int, input().split())
volume = list(map(int, input().split()))

dp = [set(), set()]
dp[0].add(s)

for i, v in enumerate(volume):
    if len(dp[i % 2]) == 0:
        print(-1)
        exit()
    dp[(i + 1) % 2] = set()
    for p in dp[i % 2]:
        if 0 <= p + v <= m:
            dp[(i + 1) % 2].add(p + v)
        if 0 <= p - v <= m:
            dp[(i + 1) % 2].add(p - v)
if len(dp[n % 2]) == 0:
    answer = -1
else:
    answer = max(dp[n % 2])
print(answer)

마지막 곡의 최대 볼륨값을 구하는 거였는데,
1. 전체 볼륨에 대한 최대값을 구해서
2. N=1인 경우에 대한 예외처리를 해주지 않아서 계속 틀렸습니다 폭탄을 맞았다.. 어렵진 않았는데 집중 못해서 헤맨 문제