문제 링크
https://www.acmicpc.net/problem/11570
🛠️ 미해결
- 풀이시간 : 2시간 이상...
- 어림 없는 풀이 : 2시간동안 삽질만 할 정도로 점화식을 어떻게 세울지 감도 안왔으며 dp 문제라고 생각도 못했었다. 답을 보고도 어떻게 푸는건지 한참을 해석할 정도로 와닿지 않았다. 하지만 풀이 방식에서 배울 것이 많다고 느꼈다.
- 현재의 해를 통해 다음 해를 : 현재의 해를 통해서 다음 해를 갱신해 나가는 방식, 즉 현재의 해에 다음 해로 이어지는 상황이 무엇인지 살펴보고 이를 갱신해 나가는 방식을 눈으로 배웠다. 상황을 생각해 나가려고 노력하는 것이다. 현재의 해에서 어떻게 하면 다음 해로 나아갈 수 있을까? 그리고 그것은 어떠한 조건을 나아갈 수 있을까라는 것이다.
- 점화식을 먼저 세워야 하는 이유 : 현재의 해를 통해 다음 해를 만들던 현재의 해를 통해 전의 해로 이루는 방법을 구성하더 중요한 것은 현재의 dp가 무엇인지 먼저 정의하려고 하고 이에 대해 점화식을 구성하는 것이라는 것이다. 이 단계가 가장 중요하며 시간이 가장 오래걸리고 이것을 세운다면 나머지 과정은 단순한 조건 맞추기 같다는 것이다.
- 습관의 개선 : dp 문제를 접근할 때, dp가 먼저 무엇인지 정의하려고 하지 않고 현재의 해든, 전의해든 구성 조건을 찾으려고 하지 않고 예시를 똑같이 풀어해치는 방식으로 접근할 때가 있다. 예시를 풀어해치되 현재의 dp가 무엇인지를 정의하고(왠만하면 문제에서 구하라고 하는 답이 dp인 경우가많다) 점화식을 이에 따라 세우며 다음해로 나아가는 조건과 추가되거나 빠지는 것이 무엇인지, 즉 다음 해로 나아가는 방법이 무엇인지를 고민해봐야 겠다.
🕒 Python 풀이시간: x
import sys
def solve_duet(N, a):
dp = [[sys.maxsize] * (N+1) for _ in range(N+1)]
dp[0][1] = dp[1][0] = 0 # 시작점 설정
for i in range(N+1):
for j in range(N+1):
next_pos = max(i, j) + 1
if next_pos < N+1:
if i==0 or j==0:
a[0]=a[next_pos]
dp[next_pos][j] = min(dp[next_pos][j], dp[i][j] + abs(a[next_pos] - a[i]))
dp[i][next_pos] = min(dp[i][next_pos], dp[i][j] + abs(a[next_pos] - a[j]))
# for i in range(N+1):
# print(dp[i])
result = sys.maxsize
for i in range(N+1):
result = min(result, dp[i][N], dp[N][i])
return result
# 입력 처리
N = int(input())
a = [0]+list(map(int, input().split()))
# 결과 출력
print(solve_duet(N, a))상덕이와 희원의 듀엣: 힘듬 최소화하기! 🎤🎶
상덕이와 희원이가 듀엣을 부를 때, 악보를 작성하는데 이 악보는 숫자로 높낮이가 되어 있다. 이 때, 이 높낮이가 변할 때의 정도를 노래를 부를 때 힘듬이라고 표현하고 이 두 사람의 힘듬의 합이 최소가 되도록 악보에서 파트를 나누어 최솟값만을 출력하는 문제이다.
여기서 N의 범위가 2,000이기 때문에 이중 for문까지는 할 수 있다는 점을 잡을 수 있다. 이러한 범위에서 dp를 우선 파악하여 무엇인지 잡아야 하는데 이는 다음과 같다. dp[i][j]는 상덕이가 마지막음으로 i를 불렀을 때와 희원이가 마지막음으로 j를 불렀을 때의 높낮이의 최솟값이다. 그렇기 때문에 범위 N에 모든 i와 j에 대해서 구해주어야 한다.
이렇게 이중 for문으로 모든 dp를 초기화 해주는데 현재 i와 j까지를 불렀을 때를 기준으로 이 중 맨 마지막에 오는 악보에 음에 다음에 오는 음이라고 할 수 있기 때문에 max를 구해서 +1을 해준다. 이렇게 이 next번째 음에 대해서 이제 점화식을 세우면 된다. 갱신되는 음은 두가지로 희원이가 next번째를 불렀을 때와 상원이가 next 번째를 불렀을 때로 나누면 되고 dp[i][j]에 변하는 높낮이의 절대값을 더해주면 된다.
이 때, 주의해야 할 점은 한쪽음이 0이라면 즉, 아직 노래를 시작하지 다음음을 불러도 그 다음음은 답, 즉 힘듬의 정도에 포함이 되지 않기 때문에 추가되는 힘듬의 정도를 0으로 만들어주어야 하기 때문에 조정이 필요하다.
마지막으로 이렇게 구한 dp에서 한쪽이 N까지 즉, 노래를 다 불렀을 경우에서 최솟값을 찾아서 갱신해주면 된다.
이렇게 Python으로 백준의 "환상의 듀엣" 문제를 해결해보았습니다. 코드와 개념 설명을 참고하여 문제를 해결하는 데 도움이 되셨길 바랍니다! 😊
