[Python] 백준 / gold / 14226: 이모티콘

문제 링크 : https://www.acmicpc.net/problem/14226

고민하는데 꽤 오래걸린 문제. 다이나믹 프로그래밍과 BFS 조합의 문제는 항상 난이도가 높은 것 같다. 처음에 오답이 났던 이유는 이거였다.

내가 dp table 에 최솟값을 갱신해가며 값을 저장하는 로직을 짰다는 거다. 근데 중요한건 지금 손해를 보더라도 나중에 이득이 되는 경로가 있을 수 있다는 거다.

dp table 을 현재 적힌 이모티콘의 수 (node) 와 클립보드에 저장된 이모티콘 수 (clipboard) 를 둘다 고려하는 2차원 테이블로 구성해서 코드를 작성했더니 정답처리 됐다.

오답 코드

import sys
from collections import deque
S = int(sys.stdin.readline())
dp = [-1] * (2*S+1)

q = deque()
# 노드, 클립보드 수, 연산 수
q.append((1, 0, 0))
dp[1] = 0

while q:
    node, clipboard, cnt = q.popleft()

    # 클립보드에 복사, 무한 복사는 일어나지 않도록 함
    if 0 <= node <= 2*S and (clipboard != node):
        q.append((node, node, cnt + 1))

    # 삭제
    if 0 <= node-1 <= 2*S and (dp[node-1] == -1 or cnt + 1 <= dp[node-1]):
        q.append(((node - 1), clipboard, cnt + 1))
        dp[node-1] = cnt+1

    if clipboard > 0:
        # 붙여넣기
        if 0 <= node+clipboard <= 2*S and (dp[node+clipboard] == -1 or cnt + 1 <= dp[node+clipboard]):
            q.append((node+clipboard, clipboard, cnt+1))
            dp[node+clipboard] = cnt+1


print(dp[S])

dp table 에 최솟값만을 넣으려고 하면 멀리봤을 때 최소가 되는 경로를 포함하지 않게 되서 오답이 난다.

정답 코드

import sys
from collections import deque
S = int(sys.stdin.readline())
dp = [[-1]*(2*S+1) for _ in range(2*S+1)]

q = deque()
# 노드, 클립보드 수, 연산 수
q.append((1, 0, 0))
dp[1][0] = 0

while q:
    node, clipboard, cnt = q.popleft()

    # 클립보드에 복사, 무한 복사는 일어나지 않도록 함
    if 0 <= node <= 2*S and dp[node][node] == -1:
        q.append((node, node, cnt + 1))
        dp[node][node] = cnt+1

    # 삭제
    if 0 <= node-1 <= 2*S and dp[node-1][clipboard] == -1:
        q.append(((node - 1), clipboard, cnt + 1))
        dp[node-1][clipboard] = cnt+1

    if clipboard > 0:
        # 붙여넣기
        if 0 <= node+clipboard <= 2*S and dp[node+clipboard][clipboard] == -1:
            q.append((node+clipboard, clipboard, cnt+1))
            dp[node+clipboard][clipboard] = cnt+1

answer = 987654321
for x in dp[S]:
    if not x == -1 and x < answer:
        answer = x

print(answer)