문제
풀이
일단 문제를 이해하는 데 조금 시간이 걸린 것 같다. 보자마자 dp 문제임을 알았고 매우 빠르게 풀이했으나 자꾸 틀려서 막바지엔 다른 풀이의 힘을 빌렸다. 조금 아쉽지만 틀린 이유를 찾는 과정에서 큰 깨달음을 얻어서 만족스러운 문제이다.
dp는 아래의 사이클을 돌며 업데이트된다.
첫번째 곡만으로 구할 수 있는 볼륨의 최댓값
첫~두번째 곡으로 구할 수 있는 볼륨의 최댓값
...
첫~n번째 곡으로 구할 수 있는 볼륨의 최댓값
여기서, 마지막 곡으로 구할 수 있는 볼륨의 최댓값은 dp의 인덱스 를 통해 구할 수 있으며 실제 dp에 쓰이는 값은 현재까지의 곡 진행 순서 를 나타낸다.
결국 dp 테이블에서 마지막 곡 순서를 나타내는 n이 쓰여진 인덱스(들)의 최댓값을 통해 정답을 구할 수 있을 것이며 dp테이블의 크기는 최대볼륨 값 만큼 될것이다.
참고로 변수가 여러개 나오면 dp 테이블을 무엇을 기준으로 문제를 어떻게 만들어야하는 지 간혹 헷갈릴 때가 있는데(본인은 현재 문제가 그러했다😅), 그럴 땐 궁극적으로 우리가 찾고자 하는 것을 기준으로 dp의 인덱스나 값 모두를 잘 활용하여 설정해야한다.
이제 풀이 과정을 상세히 살펴보자.
예제는
2 1 4 # 총 곡 수 : 2개, 초기 볼륨 : 1, 최대 볼륨 : 4
1 2 # 각 곡의 볼륨을 나타냄
로 진행하겠다
첫번째 곡만으로 구할 수 있는 볼륨의 최댓값
문제에선 현재 볼륨이 P이고 지금 i번째 곡을 연주하기 전일 때, i번 곡은 P+V[i]나 P-V[i] 로 연주해야 한다고 하였다.
현재(초기) 볼륨은 1, 볼륨 차이 또한 1이므로 2(=1+1)와 0(=1-1)로 연주 가능하기 때문에 dp는 인덱스 0과 2를 가지는 값들이 업데이트된다. 1이 값으로 쓰여진 이유는 앞서 말했 듯 현재까지의 곡 진행 순서를 나타낸 것이기 때문이다.
dp = [1,0,1,0,0]
첫번째~두번째 곡만으로 구할 수 있는 볼륨의 최댓값
현재 볼륨은 dp값이 1인 인덱스들이 모두 후보가 될 수 있으며 볼륨 차이는 2이다.(두 번째 곡으로 넘어왔으므로) 현재 볼륨 후보군들은 인덱스 0과 2이므로 각각에 대해서 2를 더하거나 뺀 인덱스에 값을 써주면 된다.
dp = [2,0,2,0,2]
바로 위와 같은 dp 테이블을 마주했다면 아마 아주 수월하게 해당 문제를 통과했을 것이다.
❌ dp = [1,0,2,0,0] #틀린 table
그렇지만 분명 해당 예제를 넣었을 때 이런식으로 dp가 작성되었던 분이 있을 것이다. (는 나) 왜 우리 예상대로 dp 테이블이 만들어지지 않았던 것일까?
왜냐하면 dp 업데이트를 아직 현재 볼륨 후보군들의 업데이트가 진행되던 중에 바로 갱신되도록 설계하는 실수를 범했기 때문이다.
다시 말하면, 인덱스 0에 대하여 먼저 dp 업데이트를 하고나니,
dp = [1,0,2,0,0]
위와 같이 인덱스 2에 대해서 dp 업데이트를 할 수 없도록(dp값이 1인 인덱스에 한하여 dp를 업데이트하기로 하였으므로) dp가 갱신되어 버린 것이다.
따라서 본인은 이를 해결하기 위해 큐를 사용해 모든 후보군에 대한 업데이트를 일괄적으로 처리하도록 하였다.
아래는 전체 코드이다.
import sys
from collections import deque
input = sys.stdin.readline
N, s, m = map(int, input().strip().split())
n = list(map(int, input().strip().split()))
q = deque()
dp = [0] * (m + 1)
dp[s] = 1
for i in range(len(n)):
for j in range(len(dp)):
cnt = i + 1
if dp[j] == cnt:
if 0 <= j - n[i] <= m:
q.append((j, 0)) # 0은 뺄셈을 의미
if 0 <= j + n[i] <= m:
q.append((j, 1)) # 1은 덧셈을 의미
while q:
j, cal = q.popleft()
if cal == 0:
dp[j - n[i]] = cnt + 1
else:
dp[j + n[i]] = cnt + 1
for i in range(len(dp) - 1, -1, -1):
if dp[i] == N + 1:
print(i)
exit()
print(-1)깨달은 점
- 작성하고 나서 다른 풀이를 보니 큐를 사용하지 않고 dp 자체를 2차원 배열로 만들어서 각 곡마다 볼륨을 저장하는 방식이 조금 더 베이직한 것 같다. dp table을 2차원으로 구성 하는 것이 오히려 더 쉽게 생각할 수 있는 방식일 수도 있겠다는 생각을 했다. 적극적으로 활용해봐야겠다.
