알고리즘/Dynamic Programming
[DP] 백준 11058 : 크리보드 - 파이썬 Python
코딩균
2022. 3. 16. 12:22
https://www.acmicpc.net/problem/11058
생각하기
dp[N]을 N번 키보드를 눌렀을 때, 화면에 출력할 수 있는 A의 최대 개수라고 한다
먼저 각 버튼의 종류를 살펴보자면
- A를 추가 출력하기 위해 한번 누르면 된다
- ctrl + A, ctrl + C는 출력을 위한 것이 아니라 ctrl + V의 선행 조건이다 -> ctrl+A ctrl+C ctrl+V를 모두 묶는다?
N인 상태에서 어떻게 하면 최대인 개수를 찾아낼 수 있는지 생각해본다
- 이전 N-1 상태에서 A를 눌러서 A를 추가하는 것 -> dp[N-1] + 1
- ctrl + V를 한번 눌러서 복사본을 추가하는 것
- 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])