[백준] 14226번:이모티콘 (python 파이썬)

문제

www.acmicpc.net/problem/14226

14226번: 이모티콘

 

풀이

deque에 (현재 모니터에 표시되어있는 이모티콘의 길이, 클립보드에 복사된 이모티콘의 길이) 를 넣어주며

deque가 빌 때 까지 반복하며 복사, 붙혀넣기, 삭제의 과정을 반복해준다.

 

소스코드

from collections import deque

dp = [[-1]*1001 for _ in range(1001)]
dp[1][0] = 0
que = deque()
que.append((1,0))

s = int(input())

while que:
    mlen, clen = que.popleft()
    if dp[mlen][mlen] == -1:
        dp[mlen][mlen] = dp[mlen][clen]+1
        que.append((mlen, mlen))
    if mlen+clen<=s and dp[mlen+clen][clen]==-1:
        dp[mlen+clen][clen] = dp[mlen][clen]+1
        que.append((mlen+clen, clen))
    if mlen-1>0 and dp[mlen-1][clen]==-1:
        dp[mlen-1][clen] = dp[mlen][clen]+1
        que.append((mlen-1, clen))


ans = -1
for i in range(s):
    if dp[s][i]!=-1:
        if ans==-1 or ans>dp[s][i]:
            ans = dp[s][i]
print(ans)