[코테] 백준 다이나믹 프로그래밍 11058번 문제

11058번 : 크리보드

문제 링크

https://www.acmicpc.net/problem/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부터는 복붙을 하는게 최댓값인데 복붙하는 위치를 다르게 해서 출력되는 ‘A’가 최대인 값 갱신한다.

N = int(input())
dp = [0] * 101

# 1~6까지는 'A'를 입력하는 게 최댓값
for i in range(1, 7) :
    dp[i] = i

# 7부터는 복붙을 하는게 최댓값
for i in range(7, N+1) :
    # 복붙하는 위치를 다르게 해서 출력되는 'A'가 최대인 값 갱신
    for j in range(3, i) : 
        if i - j > 0 :
            dp[i] = max(dp[i], dp[i-j] * (j-1))

print(dp[N])