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

난이도 : GOLD IV

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

문제해결 아이디어

• 걸리는 시간의 최솟값을 구한다. 즉, 최단시간을 구해야하니 BFS로 풀면 된다.
• 3가지 연산만 사용해서 이모티콘을 S개 만든다
  즉, 화면에 이모티콘의 개수 s와 클립보드에 있는 이모티콘의 개수c를 고려해서 풀면 된다.
• 화면에 있는 이모티콘을 모두 복사해서 클립보드에 저장한다.
  • 복사 : (s,c) -> (s,s)
  • 클립보드에 있는 모든 이모티콘을 화면에 붙여넣기 한다.
  • 붙여넣기 : (s,s) -> (s+c, c)
  • 화면에 있는 이모티콘 중 하나를 삭제한다.
  • (s,s) -> (s-1, c)
  • => 모든 연산은 1초가 걸리니 모든 경로의 가중치는 1이다.
    따라서, dist[s][c] + 1 과 같이 1을 더해줘야 한다.

소스코드

import sys

from collections import deque

input = sys.stdin.readline

n = int(input())

dist = [[-1] * (n+1) for _ in range(n+1)]

dist[1][0] = 0


q = deque()
q.append((1,0))

while q:
    s,c = q.popleft()

    if s+c <= n and dist[s+c][c] == -1:
        dist[s+c][c] = dist[s][c] + 1
        q.append((s+c, c))

    if dist[s][s] == -1:
        dist[s][s] = dist[s][c] + 1
        q.append((s,s))

    if s-1 >= 0 and dist[s-1][c] == -1:
        dist[s-1][c] = dist[s][c] + 1
        q.append((s-1,c))



for i in dist[n]:
    if i == -1:
        i = 1001

answer = -1
for i in range(n+1):
    if dist[n][i] != -1:
        if answer == -1 or answer > dist[n][i]:
            answer = dist[n][i]

print(answer)