[백준] 14226(파이썬) - 이모티콘

https://www.acmicpc.net/problem/14226

14226번: 이모티콘

• 이 문제는 처음 보고 그리디인가...? 했는데 그리디가 불가능한 문제였다. 그리디를 사용해도 되나..? 하는 문제들을 보면 거의 BFS나 DP 문제인 거 같다.
• 문제를 읽어보면 최단시간을 구해야 하는데 '최단'이라는 키워드가 나오면 BFS를 생각해보는 게 좋은 거 같다.
• BFS로 풀어봐야지 했는데 감이 오질 않았었는데 현재 화면의 이모티콘 개수와 클립보드에 있는 이모티콘 개수를 각각 처리하는 방법을 생각하다가 2차원 배열을 생각했다.
• BFS + DP로 풀이를 한 거 같다.

 

• 첫 번째 연산 : 화면에 있는 이모티콘을 모두 복사해서 클립보드에 저장한다.
  복사 : (window,clipboard) -> (window,window)
• 두 번째 연산 : 클립보드에 있는 모든 이모티콘을 화면에 붙여넣기 한다.
  붙여넣기 : (window,clipboard) -> (window+clipboard, clipboard)
• 세 번째 연산 : 화면에 있는 이모티콘 중 하나를 삭제한다.
  (window,clipboard) -> (window-1, clipboard)
• => 모든 연산은 1초가 걸리니 모든 경로의 가중치는 1이다.
  따라서, dp[window][clipboard] + 1 과 같이 1을 더해줘야 한다.

import collections
import sys
from collections import deque
input = sys.stdin.readline

# 최단시간이면 BFS 문제이다.  
s = int(input())
# 숫자로 생각해서 계산해야한다.
dp = [[-1]*(s+1) for _ in range(s+1)]

#dp 스러운 bfs문제
def bfs():
    q = deque()
    q.append((1,0))
    dp[1][0] = 0

    while q:
        #현재 화면 이모티콘 개수, 클립보드 이모티콘 개수
        window,clipboard = q.popleft()

        # 1번 연산
        if dp[window][window] == -1:
            dp[window][window] = dp[window][clipboard] + 1
            q.append((window,window))
        # 2번 연산
        if window+clipboard <= s and dp[window+clipboard][clipboard] == -1:
            dp[window+clipboard][clipboard] = dp[window][clipboard] + 1
            q.append((window+clipboard,clipboard))
        # 3번 연산
        if window - 1 >=0 and dp[window-1][clipboard] == -1:
            dp[window-1][clipboard] = dp[window][clipboard] + 1
            q.append((window-1,clipboard))

bfs()
ans = dp[s][1]

for i in range(1,s):
    if dp[s][i] != -1:
        ans = min(dp[s][i],ans)
print(ans)