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

백준 14226 - 이모티콘

시간 제한 2초, 메모리 제한 512MB

# 조건

• 영선이는 매우 기쁘기 때문에, 효빈이에게 스마일 이모티콘을 S개 보내려고 한다.
• 영선이는 이미 화면에 이모티콘 1개를 입력했다.
• 이제, 다음과 같은 3가지 연산만 사용해서 이모티콘을 S개 만들어 보려고 한다.
  1. 화면에 있는 이모티콘을 모두 복사해서 클립보드에 저장한다.
  2. 클립보드에 있는 모든 이모티콘을 화면에 붙여넣기 한다.
  3. 화면에 있는 이모티콘 중 하나를 삭제한다.
• 모든 연산은 1초가 걸린다.
• 또, 클립보드에 이모티콘을 복사하면 이전에 클립보드에 있던 내용은 덮어쓰기가 된다.
• 클립보드가 비어있는 상태에는 붙여넣기를 할 수 없으며, 일부만 클립보드에 복사할 수는 없다.
• 또한, 클립보드에 있는 이모티콘 중 일부를 삭제할 수 없다.
• 화면에 이모티콘을 붙여넣기 하면, 클립보드에 있는 이모티콘의 개수가 화면에 추가된다.
• 영선이가 S개의 이모티콘을 화면에 만드는데 걸리는 시간의 최솟값을 구하는 프로그램을 작성하시오.

입력

• 첫째 줄에 S (2 ≤ S ≤ 1000) 가 주어진다.

출력

• 첫째 줄에 이모티콘을 S개 만들기 위해 필요한 시간의 최솟값을 출력한다.

# 접근 방법

• bfs를 사용해서 풀어주었다.
• 우선 영선이가 할 수 있는 행동은
  • 화면에서 클립보드로의 저장
  • 클립보드에서 화면으로의 복사
  • 화면의 이모티콘 중 하나를 삭제하는 것
• 또한, 위의 행동은 순서대로가 아닌 원하는 만큼 할 수 있다는 점을 알아야 한다.
• q에 들어가는 값은 화면의 (이모티콘 개수, 클립보드의 개수) 로 담아준다.
• 이후, q에서 값을 꺼낸 후 위의 3개의 행동을 반복하여 준다.
  • 화면에서 클립보드 복사
    • screen, clipboard => screen, screen으로 담아준다.
  • 클립보드에 있는 이모티콘 화면에 붙여넣기
    • screen, clipboard => screen + clipboard, clipboard
    • screen+clipboard가 범위 벗어나는지 체크
  • 화면에 있는 이모티콘 중 하나 삭제
    • screen, clipboard => screen-1, clipboard
    • -1을 하였을 때 0보다 큰지 체크해주기
  • 방문 배열의 범위를 벗어나는지 체크를 해주고, 방문하지 않았다면 q에 담아주고 표시해준다.
• 초기 방문 배열의 크기는 N+1 의 크기로 만들어준다.

import sys  
sys.stdin = open('input.txt')  
input = sys.stdin.readline  
from collections import deque  

def bfs():  
    # q에는 화면의 이모티콘 수, 클립보드의 이모티콘 수로 담아주기  
    q = deque()  
    q.append([1, 0])  
    while q:  
        screen, clipboard = q.popleft()  
        # 문제에 나온 순서대로 화면 이모티콘 복사해서 클립보드에 저장  
        if not visited[screen][screen]:  
            visited[screen][screen] = visited[screen][clipboard] + 1  
            q.append([screen, screen])  

        # 클립보드에서 화면에 붙여넣기  
        # 클립보드에 이모티콘 있는지 체크해주지 않아도 이미 dp에 값이 있어 중복검사 x        
        if screen + clipboard <= N and not visited[screen+clipboard][clipboard]:  
            visited[screen+clipboard][clipboard] = visited[screen][clipboard] + 1  
            q.append([screen + clipboard, clipboard])  
        # 화면에 있는 것 중 하나 지워주기  
        if screen-1 > 0 and not visited[screen-1][clipboard]:  
            visited[screen-1][clipboard] = visited[screen][clipboard] + 1  
            q.append([screen-1, clipboard])  



N = int(input())  
# dp[i][j] = i개의 화면 이모티콘과 j개의 클립보드 이모티콘  
visited = [[0] * (N+1) for _ in range(N+1)]  
visited[1][0] = 1  
bfs()  

answer = -1  
for i in visited[N]:  
    if i != 0 and (answer > i or answer == -1):  
        answer = i  
print(answer-1)

• 다른 분들의 dp 풀이를 보며 dp에 대해 더 많이 생각해보게 되었다.
• 각 지점에 도착할 수 있는 최소 시간을 time이라고 한다면 2 이상의 n값에 대하여 time[n]은 아래 3가지 경우 중 최솟값을 구할 수 있다.
  • N
    • 1초를 사용하여 이모티콘 1개를 클립보드로 복사하고 그대로 화면에 1개씩 복사한다면 2이상의 time[n]은 N이 될 수 있다.
  • time[N+1] + 1
    • 화면의 한 개를 삭제하여 N을 만들 수도 있으므로 time[N+1] + 1 또한 하나의 방법이다.
  • time[t] + N / t
    • N의 약수 t에 대해 (t, t)를 (N, t)로 만들기 위해서는 N // t 의 초가 걸리게 된다.
    • 4, 4에서 12를 만들기 위해선 12//4 초만큼 더 걸린다.
• 이제 i를 2부터, j를 2부터 하여 i의 배수만큼 위의 최솟값을 갱신해나가면 된다.
• 초기의 N초는 time배열을 만들 때 list(range(1003)) 을 통하여 미리 만들어 두었다.
• i는 현재 클립보드의 이모티콘 수, j는 화면의 이모티콘 수이다.

s = int(input())  
time = list(range(1003))  

for i in range(2, s + 1):  
    j = 2  
    while i * j <= 100:  
        time[i * j] = min(time[i * j], time[i] + j)  
        time[i * j - 1] = min(time[i * j - 1], time[i * j] + 1)  
        j += 1  

print(time[s])