백준, 이모티콘

백준, 이모티콘

 

문제

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

14226번: 이모티콘

 

 

풀이

set 자료구조를 이용해 방문표시를 해 이미 계산한 적있는 (screen, clipboard)는 또 계산하지 않도록 했다.

계산하는 순간 시간이 늘어나므로! (문제에서 원하는 건 최소 시간이므로)

또한 작업 순서를 순차적으로 하기 위해 queue 자료구조에에 작업 순서 저장해 popleft해가면서 차례로 계산해 나갔다.

 

분류

30분동안, dp로 접근해 규칙을 찾아내려고 애썼지만 별다른 규칙을 찾지 못했다.

다른 사람 코드 보고 이해한 뒤, 코드 작성!

accepted 로 분류, 추후 안보고 다시 한번 풀어봐야 겠다(복습 필수!!).

 

코드

from collections import deque

def minTimeToCreateEmotion(S):
    queue = deque([(1, 0, 0)])  # (screen, clipboard, time)
    visited = set([(1, 0)])

    while queue:
        screen, clipboard, time = queue.popleft()

        if screen == S:
            return time

        # 화면에 있는 모든 이모티콘 복사해 클립보드에 저장
        if (screen, screen) not in visited:
            queue.append((screen, screen, time + 1))
            visited.add((screen, screen))

        # 클립보드에 있는 모든 이모티콘을 화면에 붙여넣기
        if (screen + clipboard, clipboard) not in visited:
            queue.append((screen + clipboard, clipboard, time + 1))
            visited.add((screen + clipboard, clipboard))

        # 화면에 있는 이모티콘 중 하나를 삭제
        if (screen - 1, clipboard) not in visited:
            queue.append((screen - 1, clipboard, time + 1))
            visited.add((screen - 1, clipboard))

S = int(input())
print(minTimeToCreateEmotion(S))