💡막힌부분

bfs로 접근했으나 막혔다..! 이 문제에서 눈여겨 보아야 할 것은 2가지이다. 바로 현재 화면에 나타난 이모티콘의 개수와 클립보드에 저장되어 있는 이모티콘의 개수이다. 이를 어떤식으로 처리해야 할 지 몰라서 검색을 통해 해결했다. 문제 만든 사람은 진짜 천잰가싶다..

💡풀이방법

그냥 간단하게 이차원 배열로 해결하면 된다. 첫 행에는 현재 화면에 나타난 이모티콘의 개수, 둘째 행에는 클립보드에 저장된 이모티콘의 개수를 저장한다. 예를 들어, graph[3][2] = 5이면 현재 화면에 나타난 이모티콘의 개수는 3이고 클립보드에 저장된 이모티콘의 수는 2이다. 이러한 상황에 다다르기까지의 최단값이 5인 것이다.

이 때 화면에는 원하는 개수만큼의 이모티콘이 존재해도 클립보드에 저장된 이모티콘의 개수는 다를 수 있기 때문에 반드시 최소값을 구해주는 과정을 거쳐야 답을 구할 수 있다.

📝소스코드

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

S = int(input())
graph = [[-1]*(S+1) for _ in range(S+1)]
queue = deque()

def bfs():
    queue.append([1, 0])
    graph[1][0] = 0
    while queue:
    	# s는 screen, c는 clipboard
        s, c = queue.popleft()
        # 클립보드에 현재 화면에 있는 이모티콘을 복사
        if graph[s][s]==-1:
            graph[s][s] = graph[s][c]+1
            queue.append([s, s])
        # 클립보드에 있는 이모티콘을 화면에 붙여넣기
        if s+c<=S and graph[s+c][c]==-1:
            graph[s+c][c] = graph[s][c]+1
            queue.append([s+c, c])
        # 현재 화면에 있는 이모티콘 한 개 제거
        if s-1>0 and graph[s-1][c]==-1:
            graph[s-1][c] = graph[s][c]+1
            queue.append([s-1, c])
bfs()
# 최솟값을 구하는 과정
temp = graph[S][1]
for i in range(1, S+1):
    temp = min(temp, graph[S][i])
print(temp)