[python] 백준 14226 이모티콘

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

14226번: 이모티콘

 

문제해결

• 각각의 상황에서 3가지 선택지가 있다.
• 그렇지만 3가지 선택의 결과가 이전에 나왔던 상황이면(visited 된 상황) 이전의 시간이 더 적게 걸렸으므로 무시할 수 있다.
• 화면의 길이가 s가 될 때 visited[(now,clip)] 값을 출력하면 된다.

CODE

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

s = int(input())
q = deque()
# (현재 이모티콘 개수, 클립보드에 있는 개수)
q.append((1,0))
# 2차원 리스트를 만들 수 있으나 불필요한 정보가 많으므로 방문표시를 딕셔너리로 표현
visited = dict()
visited[(1,0)] = 0 # 처음 시작할 때 화면에 1가지 이모티콘이 이미 적혀있으므로 visited[(1,0)] = 0이다.

while q:
    now, clip = q.popleft()
    if now == s:
        print(visited[(now, clip)])
        break
    # 1. 화면에 있는 이모티콘 복사
    if (now, now) not in visited.keys():
        visited[(now,now)] = visited[(now,clip)] + 1
        q.append((now, now))
    # 2. 클립보드에 있는 모든 이모티콘을 화면에 붙여넣기
    if (now + clip, clip) not in visited.keys():
        visited[(now+clip, clip)] = visited[(now,clip)] + 1
        q.append((now+clip, clip))
     # 3. 화면에 있는 이모티콘 중 하나를 삭제하기
    if (now-1, clip) not in visited.keys():
        visited[(now-1, clip)] = visited[(now,clip)] + 1
        q.append((now-1, clip))