[백준/파이썬] 14226번 이모티콘

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

14226번: 이모티콘

---

문제 & 테스트 케이스

---

문제 해석

1. 현재 이모티콘 복사

2. 복사된 클립보드의 이모티콘 붙여넣기

3. 현재 이모티콘 하나 삭제

이 3가지 기능을 통해 주어진 입력의 수의 이모티콘을 만드는 문제이다.

이때 클립보드의 이모티콘이 0개일 때 붙여넣을 수 없다.

---

코드

from collections import deque
input = __import__('sys').stdin.readline

target = int(input())
copyEmo = 0
visit = [[0] * 1001 for _ in range(1001)]

def do(k, emo, cE):
    if k == 0:  # 복사
        return (emo, emo)
    elif k == 1:    # 붙여넣기
        return (emo + cE, cE)
    else:   # 삭제
        return (emo - 1, cE)

def bfs(target):
    q = deque()
    q.append((1, 0, 0))    # emo, copyEmo, cnt
    visit[1][0] = 1
    while q:
        emo, copyEmo, cnt = q.popleft()
        if emo == target:
            return cnt
        for k in range(3):
            e, cE = do(k, emo, copyEmo)
            if cE == 0 and k == 1: continue # 붙여넣을 때 복사된 값이 0인 경우
            if not(0 <= e < 1001): continue
            if visit[e][cE] == 0:
                visit[e][cE] = 1
                q.append((e, cE, cnt + 1))

print(bfs(target))

---

문제 풀이

BFS를 통해 쉽게 해결할 수 있다.

이모티콘의 개수와 복사된 이모티콘의 개수를 큐에 넣어 원하는 이모티콘의 수가 도달할 때 까지 BFS를 돌리도록 작성하였다.

 

중요한 포인트로 방문 배열을 [현재 이모티콘 수][복사된 이모티콘 수]로 2차원 배열로 지정해 방문했는지 확인하도록 확인했다.

 

추가적으로 붙여넣기 k = 1 일때, 붙여넣을 값이 0이라면 continue를 통해 큐에 넣지 않아 쓸모없는 동작을 최소로 줄여주었다.