[BOJ] 크리보드 (no.11058)

문제

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

화면에 A를 출력한다.
Ctrl-A: 화면을 전체 선택한다
Ctrl-C: 전체 선택한 내용을 버퍼에 복사한다
Ctrl-V: 버퍼가 비어있지 않은 경우에는 화면에 출력된 문자열의 바로 뒤에 버퍼의 내용을 붙여넣는다.
크리보드의 버튼을 총 N번 눌러서 화면에 출력된 A개수를 최대로하는 프로그램을 작성하시오.

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

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

🤔 생각

아 진짜 너무 맵다ㅜㅜ...

• 언제나 그렇듯 마지막 수를 생각해서 케이스를 나눠보자

메모이제이션

dp[i] : i번 눌러서 출력할 수 있는 A의 최대 개수

케이스

1. 1번을 누를 경우
   • dp[i] = dp[i-1] + 1
2. 2번을 누를 경우
   • 최대값이 될 수 없음. 무시
3. 3번을 누를 경우
   • 2번과 동일
4. 4번을 누를 경우
   • dp[i] = 2*dp[i-3]

여기서 끝이 아니다!

4번은 앞에서 계속 누르는게 가능하다. (한번 복사하면 몇번이고 붙여넣을 수 있듯)
i-4번째의 값을 복사한다고 가정하자. 그럼 i까지 총 두번 붙여넣을 것이므로, i-4의 출력값이 세배가 될 것이다.

dp[i] = 3*dp[i-4]

아래와 공식화 시킬 수 있겠다. 이중 for문으로 j라는 변수가 있다 가정한다.

dp[i] = j*dp[i-(j+1)]

지금까지 나온 값들 중 최댓값을 구하는게 점화식이 되겠다.

🔥 점화식
dp[i] = max(dp[i-1]+1, j*dp[n-(j+1)])

📌 내 풀이

import sys
input = sys.stdin.readline

N = int(input())
dp = [0]*101
dp[0] = 0; dp[1] = 1; dp[2] = 2; dp[3] = 3

for i in range(4,N+1):
    for j in range(2,i-2):
        dp[i] = max(dp[i-1]+1, j*dp[i-(j+1)], dp[i])

print(dp[N])

• j 범위 구하는게 살짝 머리 아팠는데
• 그냥 4번으로 붙여넣을 경우 최소의 경우가 기존 출력값의 몇배고 (2배)
• 최대의 경우가 몇배인지를 생각하면 된다. (i-3배)

✔ 회고

• 어렵다... 다른 DP보다도 좀 더 케이스를 나누는게 복잡했던것 같다.
• 정답이 되기 직전에서 케이스가 얼마나 있을지 고민하는 습관은 나름 들였다고 생각했는데
• 역시나 연습이 답이다. 진득하게 생각하고 짜자