[BOJ] (DP, BFS)14226번 이모티콘

 

다이나믹 프로그래밍과 BFS를 결합해서 풀어야 하는 문제다

dp배열에 전부 INF로 채우고, 재할당한 요소에 대해서 BFS를 진행하면 된다.

 

문제를 보면, -1을 뺄 수 있다 했는데, 

n=1000일때, 1001에서 1000이 되는 경우가 최솟값이 될수 있기 때문에, 배열의 크기를 1000으로 할게 아니라 1001로 해줘야 한다. 

물론 1002에서 -1을 해주는 과정을 두번 해서 1000이 되는 케이스도 있을 수 있겠다. 

일단 베열의 크기를 n+1 해주니까 정답을 맞추긴 했다. 

 

from collections import deque
import sys

input = sys.stdin.readline
INF = int(1e9)

n = int(input())

q = deque()
dp = [[INF]*(n+2) for _ in range(n//2+2)]
# clipboard, screen, time
q.append((0, 1, 0))
dp[0][1] = 0


while q:
    clip, screen, time = q.popleft()
    
    # screen to clipboard
    try:
        if screen > 0 and dp[screen][screen] > time+1:
            dp[screen][screen] = time+1
            q.append((screen, screen, time+1))
    except:
        pass
    
    # clipboard to screen
    try:
        if clip > 0 and dp[clip][clip+screen] > time+1:
            dp[clip][clip+screen] = time+1
            q.append((clip, clip+screen, time+1))
    except:
        pass
    
    # delete one element in screen
    try:
        if screen > 0 and dp[clip][screen-1] > time+1:
            dp[clip][screen-1] = time+1
            q.append((clip, screen-1, time+1))
    except:
        pass


ans = INF
for i in range(len(dp)):
    ans = min(ans, dp[i][n])

print(ans)

 

 

 

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

14226번: 이모티콘