백준 14226번 : 이모티콘 in Python

14226번: 이모티콘

 

www.acmicpc.net

이 문제는 이모티콘 1개에서 시작해 이모티콘 전체를 클립보드에 저장하는 연산, 클립보드에 있는 모든 이모티콘을 화면에 붙여넣는 연산, 화면에 있는 이모티콘 중 하나 삭제하는 연산으로 총 3가지 연산을 이용해 S개의 이모티콘을 만드는 최소한의 횟수를 구하는 문제이다.

이를 해결하기 위해서는 dynamic programming을 이용하는데, 각 자연수 n에 대해 n개의 이모티콘을 만들기 위한 연산 횟수의 최솟값을 n번째 인덱스에 저장하는 배열 dp를 만든다. 이때 이모티콘을 한 개씩 빼는 연산도 고려해 dp의 크기는 넉넉하게 2*S+1로 한다. 초기값은 INF로 하되, dp[1]의 경우 연산을 할 필요가 없으므로 초기값을 0으로 한다.

그 다음 클립보드에 복사한 이모티콘의 개수 i에 따라 순회하면서 이모티콘을 복사함으로써 n개의 이모티콘을 만드는 경우와 기존에 저장되어있는 dp[n]을 비교해 더 작은 값으로 수정한다. 특히 이 경우 n이 i의 배수인 경우에 대해서만 고려하는데, 이는 클립보드에 i개의 이모티콘을 모두 복사한 뒤 여러 번 i개의 이모티콘을 복사하는 경우를 고려하고 있기 때문이다. 이를 모두 마친 경우 화면에 있는 이모티콘을 하나 없애는 연산도 고려한다.

이를 코드로 구현하면 다음과 같다.

import sys
S = int(input())
# 각 자연수 n마다 n개의 이모티콘을 만드는 연산 횟수의 최솟값을 n번째 entry에 저장하는 배열
dp = [sys.maxsize for _ in range(2*S+1)]
# 초기값 설정
dp[1] = 0
# 복사할 이모티콘의 개수에 대해 순회한다.
for i in range(1, S):
    # 이모티콘을 복사하는 경우를 고려한다.
    for j in range(1, (2*S)//i):
        dp[i*(j+1)] = min(dp[i] + j + 1, dp[i*(j+1)])
    # 이모티콘을 하나 제거하는 경우를 고려한다.
    for i in range(2*S-1, 0, -1):
        dp[i] = min(dp[i], dp[i+1]+1)
print(dp[S])