[Python] 백준 11058번 크리보드 - 다이나믹 프로그래밍(DP)

백준 홈페이지 문제와 개인적인 풀이를 작성한 글입니다.

 

백준 문제 - 11058번 : 크리보드

11058번: 크리보드

 

 

---

문제 

크리보드는 kriii가 만든 신기한 키보드이다. 크리보드에는 버튼이 4개만 있으며, 하는 역할은 다음과 같다.

1. 화면에 A를 출력한다.
2. Ctrl-A: 화면을 전체 선택한다.
3. Ctrl-C: 전체 선택한 내용을 버퍼에 복사한다.
4. Ctrl-V: 버퍼가 비어있지 않은 경우에는 화면에 출력된 문자열의 바로 뒤에 버퍼의 내용을 붙여넣는다.

크리보드의 버튼을 총 N번 눌러서 화면에 출력된 A개수를 최대로하는 프로그램을 작성하시오.

 

입력 

첫째 줄에 N(1 ≤ N ≤ 100)이 주어진다.

 

출력

크리보드의 버튼을 총 N번 눌러서 화면에 출력할 수 있는 A 개수의 최댓값을 출력한다.

 

힌트

N = 3인 경우에 A, A, A를 눌러 A 3개를 출력할 수 있다.

N = 7인 경우에는 A, A, A, Ctrl-A, Ctrl-C, Ctrl-V, Ctrl-V를 눌러 9개를 출력할 수 있다.

N = 11인 경우에는 A, A, A, Ctrl-A, Ctrl-C, Ctrl-V, Ctrl-V, Ctrl-A, Ctrl-C, Ctrl-V, Ctrl-V 를 눌러 27개를 출력할 수 있다.

 

예제 입력 1	예제 출력 1
3	3

 

예제 입력 2	예제 출력 2
7	9

 

예제 입력 3	예제 출력 3
11	27

 

코드

import sys
input = sys.stdin.readline

n = int(input())

dp = [0] * 101

for i in range(6):
  dp[i] = i


for i in range(6, n + 1):
  dp[i] = max(dp[i - 3] * 2, max(dp[i - 4] * 3, dp[i - 5] * 4))

print(dp[n])

 

해설

다이나믹 프로그래밍 (DP) 의 핵심은 점화식을 만드는 것 입니다. 위의 문제를 봅시다.

Ctrl-A, Ctrl-C, Ctrl-V 를 한 세트로 보고 이것을 수행해야 최댓값이 나올 수 있는 확률이 있다.

그렇기 때문에 아래 3 가지 경우만 고민하면 됩니다.

1. 3번째 전, 전체, 복사, 붙여넣기
   dp[ i - 3 ] , Ctrl-A, Ctrl-C, Ctrl-V = dp[ i - 3 ] * 2
2. 4번째 전, 전체, 복사, 붙여넣기, 붙여넣기
   dp[ i - 4 ] , Ctrl-A, Ctrl-C, Ctrl-V, Ctrl-V = dp[ i - 4 ] * 3
3. 5번째 전, 전체, 복사 붙여넣기, 붙여넣기, 붙여넣기
   dp[ i - 5 ] , Ctrl-A, Ctrl-C, Ctrl-V, Ctrl-V, Ctrl-V = dp[i - 5] * 4

이런 경우의 수 중 최댓값을 뽑아내면 정답입니다. 간단하게 풀 수 있습니다.