[DP] 백준 11058 : 크리보드 - 파이썬 Python

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

11058번: 크리보드

 

생각하기

dp[N]을 N번 키보드를 눌렀을 때, 화면에 출력할 수 있는 A의 최대 개수라고 한다

 

먼저 각 버튼의 종류를 살펴보자면

• A를 추가 출력하기 위해 한번 누르면 된다
• ctrl + A, ctrl + C는 출력을 위한 것이 아니라 ctrl + V의 선행 조건이다 -> ctrl+A ctrl+C ctrl+V를 모두 묶는다?

 

N인 상태에서 어떻게 하면 최대인 개수를 찾아낼 수 있는지 생각해본다

1. 이전 N-1 상태에서 A를 눌러서 A를 추가하는 것 -> dp[N-1] + 1
2. ctrl + V를 한번 눌러서 복사본을 추가하는 것 
3. ctrl + V를 여러번 눌러서 복사본을 추가하는 것

 

구현하기

위의 2,3번 방법을 일반화 / 점화식화 해본다면

ctrl+V를 누른다는 것은 복사 시점의 것을 반복한다는 뜻

ctrl+V를 누르기 위해서는 ctrl+A ctrl+C가 앞에 선행되어야 함 -> 앞에 두단계가 깔고 들어간다

 

만약 한번 ctrl+V를 누른다면

dp[N] = dp[N-3] * 2

 

만약 여러번 ctrl+V를 누른다면

dp[N] = dp[N - (k+2)] * (k+1) 

1 <= k <= N-1

 

시간복잡도

각 status에서 아래 status-1번을 돌면서 dp를 쌓아가기 때문에

O(N^2)이고

N이 최대 100이므로 충분히 1초 안에 해결할 수 있다

 

 

N = int(input())

dp = [0] * (N+1)
dp[1] = 1

for i in range(2, N+1):
    max_cnt = i # A만 계속 쭉 눌렀을 때
    max_cnt = max(max_cnt, dp[i-1]+1) # 방법 1 ) A를 한번 눌렀을 때
    for k in range(1, i):
        max_cnt = max(max_cnt, dp[i-(k+2)]*(k+1)) # 방법 2,3 ) ctrl+v 한번 or 두번 이상 눌렀을 때

    dp[i] = max_cnt



print(dp[N])