[백준] 11058번 > 크리보드

https://www.acmicpc.net/problem/11058

11058번: 크리보드

문제

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

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

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

입력

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

출력

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

 

---

풀이

 

1~6까지는 A를 하나씩 출력하는 것이 최대 횟수이다.

문제를 해결하기위해 생각해야할 경우는 7부터이다. 힌트를 살펴보면 일정한 규칙이 존재하는 것을 볼 수 있다.

먼저, 전체를 선택하고 복사하고 복사한 것을 출력하는 것까지 총 3번의 단계가 필요하다. 따라서 컨트롤+v를 한번 누른경우, 두번 누른경우, 세번 누른경우 중 max값을 선택하면 된다.

점화식 : dp[i] = max ( dp[i-3]*2, dp[i-4]*3, dp[i-5]*4) 

3번의 단계가 필요하므로 i-3부터 시작

 

import sys
input = sys.stdin.readline

n = int(input())
dp = [0 for _ in range(101)]
dp[1] = 1; dp[2] = 2; dp[3] = 3; dp[4] = 4; dp[5] = 5; dp[6] = 6
for i in range(7, 101):
    dp[i] = max(dp[i - 3] * 2, dp[i - 4] * 3, dp[i - 5] * 4)
print(dp[n])