백준: 14226 이모티콘

문제

14226번: 이모티콘

 

문제 풀이

 이모티콘을 출력하는데 걸리는 최소 시간은 이전에 다룬 1697 숨바꼭질 문제와 같이 트리의 가지를 뻣어나가며 정답을 찾을 수 있다. 이 문제도 마찬가지로 복사, 붙여넣기, 삭제와 같이 3가지의 경우로 가지를 뻣어나가면 된다. 가지를 뻣어나갈 때 현재 다음과 같은 처리가 필요하다.

 

• 현재 모니터에 표시된 이모티콘이 S보다 많을 경우 큐에 삽입할 필요가 없다.
• 모니터에 표시된 이모티콘이 0보다 작은 경우도 마찬가지이다.
• 가지를 뻣어나가며 현재 표시된 이모티콘을 누적한다.

 

코드

from sys import stdin
from collections import deque


def bfs(start):
    q = deque([start])

    while q:
        m, c = q.popleft()

        if m == s:
            return check[m][c]

        for n_m, n_c in \
                (m, m), (m + c, c), (m - 1, c):
            if 0 <= n_m <= s and not check[n_m][n_c]:
                q.append([n_m, n_c])
                check[n_m][n_c] = check[m][c] + 1


if __name__ == '__main__':
    MAX = 1001
    s = int(stdin.readline())
    check = [[0] * MAX for _ in range(MAX)]
    print(bfs([1, 0]))