문제
영선이는 매우 기쁘기 때문에, 효빈이에게 스마일 이모티콘을 S개 보내려고 한다.
영선이는 이미 화면에 이모티콘 1개를 입력했다. 이제, 다음과 같은 3가지 연산만 사용해서 이모티콘을 S개 만들어 보려고 한다.
- 화면에 있는 이모티콘을 모두 복사해서 클립보드에 저장한다.
- 클립보드에 있는 모든 이모티콘을 화면에 붙여넣기 한다.
- 화면에 있는 이모티콘 중 하나를 삭제한다.
모든 연산은 1초가 걸린다. 또, 클립보드에 이모티콘을 복사하면 이전에 클립보드에 있던 내용은 덮어쓰기가 된다. 클립보드가 비어있는 상태에는 붙여넣기를 할 수 없으며, 일부만 클립보드에 복사할 수는 없다. 또한, 클립보드에 있는 이모티콘 중 일부를 삭제할 수 없다. 화면에 이모티콘을 붙여넣기 하면, 클립보드에 있는 이모티콘의 개수가 화면에 추가된다.
영선이가 S개의 이모티콘을 화면에 만드는데 걸리는 시간의 최솟값을 구하는 프로그램을 작성하시오.
입력
첫째 줄에 S (2 ≤ S ≤ 1000) 가 주어진다.
출력
첫째 줄에 이모티콘을 S개 만들기 위해 필요한 시간의 최솟값을 출력한다.
예제 입력 1
2
예제 출력 1
2
예제 입력 2
4
예제 출력 2
4
코드
import sys
from collections import deque
S = int(input())
# dp[i][j] = x : 화면에 있는 이모티콘의 갯수 i개, 클립보드에 있는 이모티콘의 갯수 j개 일때 걸린 시간 x초
dp = [[-1] * 1001 for _ in range(1001)]
dp[1][0] = 0
q = deque([(1, 0)])
# 각 연산은 1초가 소요
while q:
i, j = q.popleft()
# 화면에 있는 i개의 이모티콘을 클립보드에 붙이는 경우
if i <= 1000:
if dp[i][i] == -1:
dp[i][i] = dp[i][j] + 1
q.append((i, i))
# 클립보드에 있는 j개의 이모티콘을 화면에 붙이는 경우
if i + j <= 1000:
if dp[i + j][j] == -1:
dp[i + j][j] = dp[i][j] + 1
q.append((i + j, j))
# 화면에서 이모티콘을 1개 삭제하는 경우
if i - 1 >= 0:
if dp[i - 1][j] == -1:
dp[i - 1][j] = dp[i][j] + 1
q.append((i - 1, j))
if i == S: break
ans = sys.maxsize
for y in dp[S]:
if y != -1: ans = min(ans, y)
print(ans)
생각정리
S : 입력값
dp : 화면과 클립보드를 표현할 2차원 리스트, dp[i][j] = x : 화면에 있는 이모티콘의 갯수 i개, 클립보드에 있는 이모티콘의 갯수j개 일때 걸린 시간 x초
q : i, j 를 BFS로 탐색하는 deque
ans : 결과값
1. BFS를 이용해 세 가지 경우를 탐색하여 deque에 넣어준다. (이때 각 연산은 1초가 소요)
- 화면에 있는 i개의 이모티콘을 클립보드에 붙이는 경우 => dp[i][i] = dp[i][j] + 1
문제에서 클립보드에 이모티콘을 붙일 경우 덮어씌워진다고 하였기 때문에 클립보드도 i개의 이모티콘이 된다.
- 클립보드에 있는 j개의 이모티콘을 화면에 붙이는 경우 => dp[i+j][j] = dp[i][j] + 1
- 화면에서 이모티콘을 1개 삭제하는 경우 => dp[i - 1]j] = dp[i][j] + 1
2. 화면에 있는 이모티콘의 갯수가 S개 일때까지 deque에 (i, j)를 넣어주면서 1의 과정 반복
3. 화면에 있는 이모티콘의 갯수가 S개 일때 dp[S] 에서 최소값을 결과로 출력(-1은 초기값이므로 제외)
'문제풀이 > DP' 카테고리의 다른 글
[파이썬] [DP] 백준 10844 쉬운계단수 (0) | 2022.01.28 |
---|---|
[파이썬] [DP] 백준 1932 정수 삼각형 (0) | 2022.01.28 |
[파이썬] [DP] 백준 2193 이친수 (0) | 2022.01.27 |
[파이썬] [DP] 백준 1520 내리막 길 (0) | 2022.01.26 |
[파이썬] [DP] 백준 11054 바이토닉 부분 수열 (0) | 2022.01.26 |