백준 11058번 크리보드 | python | dp

문제

링크

풀이

해당 문제는 n=100이라고 가정할 때 4가지의 선택을 100번 해야하므로 O(4^100)의 시간복잡도가 걸린다. 따라서 dp를 통해 시간을 단축해서 풀어야한다.

• 버튼 유형
  • 화면에 A를 출력하는 버튼
  • 화면 전체 선택
  • 화면 복사 (ctrl+c)
  • 화면 붙여넣기 (ctrl+v)

일단 최종 n번을 눌렀을 때 A의 최댓값을 구하는 것이므로 dp테이블의 크기는 n+1로 생성해주며, dp는 아래의 사이클을 돌며 업데이트 될 것이다.

1번 눌렀을 때 A의 최댓값
2번 눌렀을 때 A의 최댓값
...
n번 눌렀을 때의 A의 최댓값

이런 식으로 나아가다 보면 최종 값에 도달할 수 있다.

먼저 A를 출력할 수 있는 방법은 무엇일까?

1. 출력 버튼을 바로 눌러서 A 하나를 더 붙이거나,
2. 선택 - ctrl+c - ctrl+v 까지 3단계를 거쳐 버퍼에 있는 내용을 붙이거나 ( 👉🏻 계산하면 dp[i-3]*2가 될 것이다)
   둘 중 하나이다.

이제 완전한 점화식을 만들기 위해 조금 더 생각해보자.
유심히 생각해보면 버퍼에 있는 내용을 붙일 수 있는 최소 조건이 3단계인 것이지, 우리는 4단계 이전의 값을 복사해서 붙여넣을 수도 있을 것이다. 그렇게 되면 dp[i-4]*2가 된다.

5단계는 될 수 없을까? 당연히 가능하다. dp[i-5]*2가 될 것이다.

그렇다면 6은? 6을 넘어가고서부터는 그냥 출력 버튼을 바로 누르는 것이 더 크기 때문에 고려하지 않는다. (사투 끝에 알아낸 원리..)

따라서 최종 점화식은 아래와 같다

dp[i] = max(dp[i],dp[i-j]*(j-1))

사실 점화식만 보면 이해가 안 될수도 있으므로 아래 전체 코드의 주석을 통해 다시 한 번 확인해보자.

import sys

input = sys.stdin.readline
n = int(input())
dp = [0] * (n + 1)

for i in range(1, 7): # 6이하는 그냥 하나씩 출력하는 것이 최댓값임
    if i <= n:
        dp[i] = i

for i in range(7, n + 1): #7부터는 점화식에 따라 dp 업데이트 진행
    for j in range(3, i): #붙여넣는 것은 3단계가 필요하므로 최소 3부터 시작
        if i - j > 0:
            dp[i] = max(dp[i], dp[i - j] * (j - 1))

print(dp[n])

Reference

https://kibbomi.tistory.com/96