February 19, 2023

14226번: 이모티콘

문제 풀이

• 이모티콘 1개를 입력한 이후 다음 연산을 이용하여 이모티콘 S개를 만들어 보려고 한다.
  1. 화면에 있는 이모티콘을 모두 복사해서 클립보드에 저장한다.
  2. 클립보드에 있는 모든 이모티콘을 화면에 붙여넣기 한다.
  3. 화면에 있는 이모티콘 중 하나를 삭제한다.
• 각 연산은 1초가 소요될 때 S개의 이모티콘을 만들기 위한 최소 연산 수는?
• 2 ≤ S ≤ 1,000

풀이

from collections import deque

S = int(input())

visited = [[False] * 2_001 for _ in range(2_001)]

def bfs():
    q = deque()

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

    while (q):
        node, copy, cost = q.popleft()

        if (visited[node][copy]):
            continue

        if (node == S):
            print(cost)
            return

        visited[node][copy] = cost

        if (visited[node][node] == False):
            q.append((node, node, cost + 1))

        if (copy > 0 and node + copy <= 2000 and visited[node + copy][copy] == False):
            q.append((node + copy, copy, cost + 1))

        if (node - 1 >= 0 and visited[node - 1][copy] == False):
            q.append((node - 1, copy, cost + 1))

bfs()

• BFS 이용