백준 14226번 이모티콘(골드 4)

문제

영선이는 매우 기쁘기 때문에, 효빈이에게 스마일 이모티콘을 S개 보내려고 한다.

영선이는 이미 화면에 이모티콘 1개를 입력했다. 이제, 다음과 같은 3가지 연산만 사용해서 이모티콘을 S개 만들어 보려고 한다.

1. 화면에 있는 이모티콘을 모두 복사해서 클립보드에 저장한다.
2. 클립보드에 있는 모든 이모티콘을 화면에 붙여넣기 한다.
3. 화면에 있는 이모티콘 중 하나를 삭제한다.

모든 연산은 1초가 걸린다. 또, 클립보드에 이모티콘을 복사하면 이전에 클립보드에 있던 내용은 덮어쓰기가 된다. 클립보드가 비어있는 상태에는 붙여넣기를 할 수 없으며, 일부만 클립보드에 복사할 수는 없다. 또한, 클립보드에 있는 이모티콘 중 일부를 삭제할 수 없다. 화면에 이모티콘을 붙여넣기 하면, 클립보드에 있는 이모티콘의 개수가 화면에 추가된다.

영선이가 S개의 이모티콘을 화면에 만드는데 걸리는 시간의 최솟값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 S (2 ≤ S ≤ 1000) 가 주어진다.

출력

첫째 줄에 이모티콘을 S개 만들기 위해 필요한 시간의 최솟값을 출력한다.

사고(고민) 과정

처음에 이미 화면에 이모티콘을 입력한 상태임—>그럼 지금 클립보드에는 이모티콘이 있는 거임? 없는 거임?

(처음에 이게 헷갈렸음. 화면에 이모티콘이 입력되었다는 말은, 그 전에 임티를 복사해서 클립보드에 넣었다는 얘기니까)

근데 gpt는 초기 상태를 화면 : 1개, 클립보드 : 0개, 시간 : 0초 라고 가정함. 왜냐하면 모든 연산은 1초가 걸리고, 복사를 하지 않으면 클립보드는 계속 비어있다고 서술되어 있으므로, 우리는 복사 연산을 실행한 적이 없기 때문에 클립보드는 자동으로 채워지지 않은 상태로 본 것.

초기 상태(화면 : 1개, 클립보드 : 0개, 시간 : 0초)에서 시작해서 최소 시간으로 목표를 달성하라는 문제니까 최단 경로 탐색(BFS)임 - 모든 기능이 다 1초로 셋팅되어있으니깐

기능 3가지

1. 복사 및 저장(1초) —> 이전 내용은 덮어쓰기 됨
2. 붙여넣기(1초) —> 클립보드가 비어있으면 붙여넣기 불가. 일부도 불가.
3. 삭제(1초) —> 클립보드는 삭제 불가

상태는 (화면에 있는 임티 수, 클립보드에 있는 임티 수) 로 정의하고

BFS를 통해 각각의 상태에 도달하는 최소 시간을 계산

현재 상태가 (화면, 클립보드)일 때 가능한 다음 선택

1. 복사 ((화면, (클립보드 —> 화면))
2. 붙여넣기((화면 —> 화면+클립보드), 클립보드) 단, 클립보드≥ 0
3. 삭제((화면 —> 화면 -1), 클립보드) 단, 화면 ≥1

풀이 방법

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

S = int(input())
MAX = 1001 # S <= 1000

visited = [[False] * MAX for _ in range(MAX)]
#visited[화면][클립보드] = True면 방문한 상태임

q = deque()
q.append((1,0,0))
visited[1][0] = True
#초기상태

while q:
	screen, clipboard, time = q.popleft()
	if screen == S:
		print(time)
		break
		
	# 1. 복사
	if not visited[screen][screen]:
		visited[screen][screen] = True
		q.append((screen, screen, time + 1))
		
	# 2. 붙여넣기
	if clipboard > 0 and screen+clipboard < MAX:
		if not visited[screen + clipboard][clipboard]:
			visited[screen + clipboard][clipboard] = True
			q.append((screen + clipboard, clipboard, time + 1))
			
	# 3. 삭제
	if screen > 0 and not visited[screen - 1][clipboard]:
		visited[screen-1][clipboard] = True
		q.append((screen-1, clipboard, time + 1))

 

풀이 시 중점 고려 사항/핵심 문법 정리 등

if not visited[screen][screen]:
    visited[screen][screen] = True
    q.append((screen, screen, time + 1))
'''
설명
지금 화면에 있는 이모티콘 개수를 클립보드에 복사하는 거
즉, screen → clipboard로 덮어쓰기됨
복사 후에도 화면은 그대로니까 (screen, screen) 상태가 됨

왜 visited[screen][screen]을 체크할까? 이미 (화면: screen, 클립보드: screen) 상태를 방문했으면,
→ 다시 그 상태로 돌아가는 건 시간 낭비
그래서 처음 가는 상태만 큐에 넣는 거임 (= BFS에서 최단 시간을 보장하기 위해 중복 방문 방지)
'''

if clipboard > 0 and screen + clipboard < MAX:
    if not visited[screen + clipboard][clipboard]:
        visited[screen + clipboard][clipboard] = True
        q.append((screen + clipboard, clipboard, time + 1))
'''
설명
클립보드에 이모티콘이 clipboard개 있으면, 그만큼 화면에 추가됨
그래서 screen + clipboard가 됨
클립보드는 그대로 유지됨

조건이 두 개인 이유:
clipboard > 0:
→ 클립보드가 비었으면 붙여넣을 게 없으니까 붙여넣기 못 함
screen + clipboard < MAX:
→ 이모티콘이 너무 많아지면 리스트 범위를 벗어날 수 있으므로 제한
'''

if screen > 0 and not visited[screen - 1][clipboard]:
    visited[screen - 1][clipboard] = True
    q.append((screen - 1, clipboard, time + 1))
'''
설명
이모티콘 하나 삭제하면, 화면에 있던 것만 줄어듦
클립보드는 그대로

조건 screen > 0이 필요한 이유
화면에 이모티콘이 0개이면 삭제 못 함
0 이하로 떨어지면 말이 안 되니까 조건 체크
'''