[백준] 14226(파이썬) - 이모티콘

resilient

·

2021. 7. 26. 16:35

728x90
반응형

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

 

14226번: 이모티콘

영선이는 매우 기쁘기 때문에, 효빈이에게 스마일 이모티콘을 S개 보내려고 한다. 영선이는 이미 화면에 이모티콘 1개를 입력했다. 이제, 다음과 같은 3가지 연산만 사용해서 이모티콘을 S개 만

www.acmicpc.net

  • 이 문제는 처음 보고 그리디인가...? 했는데 그리디가 불가능한 문제였다. 그리디를 사용해도 되나..? 하는 문제들을 보면 거의 BFS나 DP 문제인 거 같다.
  • 문제를 읽어보면 최단시간을 구해야 하는데 '최단'이라는 키워드가 나오면 BFS를 생각해보는 게 좋은 거 같다.
  • BFS로 풀어봐야지 했는데 감이 오질 않았었는데 현재 화면의 이모티콘 개수와 클립보드에 있는 이모티콘 개수를 각각 처리하는 방법을 생각하다가 2차원 배열을 생각했다.
  • BFS + DP로 풀이를 한 거 같다.

 

  • 첫 번째 연산 : 화면에 있는 이모티콘을 모두 복사해서 클립보드에 저장한다.
    복사 : (window,clipboard) -> (window,window)
  • 두 번째 연산 : 클립보드에 있는 모든 이모티콘을 화면에 붙여넣기 한다.
    붙여넣기 : (window,clipboard) -> (window+clipboard, clipboard)
  • 세 번째 연산 : 화면에 있는 이모티콘 중 하나를 삭제한다.
    (window,clipboard) -> (window-1, clipboard)
  • => 모든 연산은 1초가 걸리니 모든 경로의 가중치는 1이다.
    따라서, dp[window][clipboard] + 1 과 같이 1을 더해줘야 한다.
import collections
import sys
from collections import deque
input = sys.stdin.readline

# 최단시간이면 BFS 문제이다.  
s = int(input())
# 숫자로 생각해서 계산해야한다.
dp = [[-1]*(s+1) for _ in range(s+1)]

#dp 스러운 bfs문제
def bfs():
    q = deque()
    q.append((1,0))
    dp[1][0] = 0

    while q:
        #현재 화면 이모티콘 개수, 클립보드 이모티콘 개수
        window,clipboard = q.popleft()

        # 1번 연산
        if dp[window][window] == -1:
            dp[window][window] = dp[window][clipboard] + 1
            q.append((window,window))
        # 2번 연산
        if window+clipboard <= s and dp[window+clipboard][clipboard] == -1:
            dp[window+clipboard][clipboard] = dp[window][clipboard] + 1
            q.append((window+clipboard,clipboard))
        # 3번 연산
        if window - 1 >=0 and dp[window-1][clipboard] == -1:
            dp[window-1][clipboard] = dp[window][clipboard] + 1
            q.append((window-1,clipboard))

bfs()
ans = dp[s][1]

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

 

 

 

 

 

 

반응형