14226번: 이모티콘
영선이는 매우 기쁘기 때문에, 효빈이에게 스마일 이모티콘을 S개 보내려고 한다. 영선이는 이미 화면에 이모티콘 1개를 입력했다. 이제, 다음과 같은 3가지 연산만 사용해서 이모티콘을 S개 만
www.acmicpc.net
문제
영선이는 매우 기쁘기 때문에, 효빈이에게 스마일 이모티콘을 S개 보내려고 한다.
영선이는 이미 화면에 이모티콘 1개를 입력했다. 이제, 다음과 같은 3가지 연산만 사용해서 이모티콘을 S개 만들어 보려고 한다.
- 화면에 있는 이모티콘을 모두 복사해서 클립보드에 저장한다.
- 클립보드에 있는 모든 이모티콘을 화면에 붙여넣기 한다.
- 화면에 있는 이모티콘 중 하나를 삭제한다.
모든 연산은 1초가 걸린다. 또, 클립보드에 이모티콘을 복사하면 이전에 클립보드에 있던 내용은 덮어쓰기가 된다. 클립보드가 비어있는 상태에는 붙여넣기를 할 수 없으며, 일부만 클립보드에 복사할 수는 없다. 또한, 클립보드에 있는 이모티콘 중 일부를 삭제할 수 없다. 화면에 이모티콘을 붙여넣기 하면, 클립보드에 있는 이모티콘의 개수가 화면에 추가된다.
영선이가 S개의 이모티콘을 화면에 만드는데 걸리는 시간의 최솟값을 구하는 프로그램을 작성하시오.
입력
첫째 줄에 S (2 ≤ S ≤ 1000) 가 주어진다.
출력
첫째 줄에 이모티콘을 S개 만들기 위해 필요한 시간의 최솟값을 출력한다.
코드
from collections import deque
s = int(input())
dp = [[int(1e9)]*(s+1) for _ in range(s+1)]
q = deque([(1, 0)])
dp[1][0] = 0
while q:
screen, clip = q.popleft()
t = dp[screen][clip]
for ns, nc in [(screen, screen), (screen+clip, clip), (screen-1, clip)]:
if 0 <= ns < s+1 and dp[ns][nc] > t+1:
dp[ns][nc] = t+1
q.append((ns, nc))
print(min(dp[s]))
BFS와 DP를 이용하여 풀었다.
dp[i][j]에는 화면에 i개, 클립보드에 j개의 이모티콘이 만들어지는데 걸리는 시간의 최솟값을 저장한다.
'문제풀이 > DP' 카테고리의 다른 글
[Python/파이썬] 백준 4811번 알약 (0) | 2023.09.13 |
---|---|
[Python/파이썬] 백준 13707번 합분해 2 (0) | 2023.09.08 |
[Python/파이썬] 백준 17265번 나의 인생에는 수학과 함께 (0) | 2023.08.29 |
[Python/파이썬] 백준 11909번 배열 탈출 (0) | 2023.08.24 |
[Python/파이썬] 백준 13910번 개업 (1) | 2023.08.18 |