[#1495] 기타리스트

문제

#1495 기타리스트
Silver1
적용 알고리즘: 다이나믹 프로그래밍

---

풀이 방법

• 현재 음량에서 가능한 음량 수만을 고려한다.
• 계산에는 현재 음량과 그 다음 음량만 고려(저장)하면 된다. 다 저장하는 경우 메모리 초과 발생

코드 흐름

1. 초기 음량(0번째)을 저장한다. (S)
2. 1번째 음량은 “초기 음량 + 1번째 음량 폭” 이거나 “초기 음량 - 1번째 음량 폭”이다. 두 경우를 계산하여 범위 내에 들어오는 음량만 저장한다.
3. 2번째 음량은 가능한 모든 1번째 음량에 대해서 “1번째 음량 - 1번째 음량 폭” 이거나 “1번째 음량 + 1번째 음량 폭”이다. 마찬가지로 범위 내에 들어오는 음량을 저장한다.
4. i번째와 i+1번째 음량의 관계는 마찬가지로 2, 3번을 따른다. 만일 진행 도중 가능한 음량이 없는 경우, -1을 출력한다.
5. 끝에 다다르면 가장 큰 음량을 출력한다.

코드

첫 번쨰 시도(메모리 초과)

N, S, M = map(int, input().split())
vol = list(map(int, input().split()))
vol.insert(0, 0)

temp = []
if (0 <= S - vol[1] <= M):
    temp.append(S - vol[1])
if (0 <= S + vol[1] <= M):
    temp.append(S + vol[1])

vol_dict = {}
vol_dict[0] = [S]
vol_dict[1] = temp

flag = 0

for i in range(2, N + 1):
    if (len(vol_dict[1]) == 0):
        flag = 1
        break
    temp = []
    for j in range(len(vol_dict[i - 1])):
        if (0 <= vol_dict[i - 1][j] - vol[i] <= M):
            temp.append(vol_dict[i - 1][j] - vol[i])
        if (0 <= vol_dict[i - 1][j] + vol[i] <= M):
            temp.append(vol_dict[i - 1][j] + vol[i])

    if len(temp) == 0:
        flag = 1
        break
    vol_dict[i] = temp

if (flag == 1):
    print(-1)
else:
    print(max(vol_dict[N]))

일단 더럽게 코딩하고 제출하고 맞으면 다듬을려고 했는데 틀려버렸다;;; 나름 점화식을 세워서 했다고 했는데 메모리초과가 났다… 아무래도 모든 상태의 볼륨 값을 다 저장해서 그런 것 같다.

두 번쨰 시도(해결 완료)

N, S, M = map(int, input().split())
vol = list(map(int, input().split()))
vol.insert(0, 0)

cur_vol = set()

flag = 0
cur_vol.add(S)

for i in range(1, N + 1):
    next_vol = set()
    for j in cur_vol:
        if (0 <= j - vol[i] <= M):
            next_vol.add(j - vol[i])
        if (0 <= j + vol[i] <= M):
            next_vol.add(j + vol[i])
    if not next_vol:
        flag = 1
        break
    cur_vol = next_vol

if flag == 1:
    print(-1)
else:
    print(max(cur_vol))

현재 볼륨 값과 그 다음 볼륨 값만 저장하여 메모리 초과 문제 해결.

체감 난이도: 4.7/5
아니 다이나믹 프로그래밍 문제 나름 익숙해졌다고 생각했는데 나는 아직 멀었구나… 이런 실버도 끙끙대다니 문제를 좀 더 열심히 풀어야겠다…