[DP] 백준 11058 크리보드 python

📄 백준 11058 크리보드  📄

www.acmicpc.net/problem/11058

11058번: 크리보드

---

🤔 문제 풀이  🤔

버튼 1을 누르는 경우 dp[n] = dp[n - 1] + 1

버튼 2, 3을 누르는 경우는 크기가 증가하지 않으므로 최댓값이 될 수 없다.

버튼 4를 누르는 경우는 ctrl + A, ctrl + C인 2, 3번 버튼이 선행되어야 하므로 총 3개의 버튼 입력이 필요하다. (dp[n] = dp[n - 3] * 2)

이 때 버튼 4를 연속해서 두번 누르면 3배가 되는 것과 같으므로 dp[n] = dp[n - 4] * 3

이런 식으로 버튼 4를 연속해서 누르는 식을 구하게 되면 dp[n] = dp[n - j] * (j - 1) 이 나오게 된다.

 

n이 1 ~ 6까지는 그냥 버튼 1만 눌러도 최댓값이 나온다. dp[1 ~ 6] = 1 ~ 6

7부터는 복사 붙여넣기를 적용해준다. dp[i] = max(dp[i], dp[i - j] * (j - 1)) (단, i - j > 0)

 

7이후부터는 n에서 버퍼에 들어가 있는 크기가 1보다는 크므로 dp[n] = dp[n - 1] + 1은 최댓값이 될수 없다. 이걸로 버튼 1개를 소모할 바엔 그냥 붙여넣기 한번 더 해주는 것이 크기를 더 늘릴 수 있다.

 

---

⌨️ 코드 ⌨️

n = int(input())

dp = [0] * (n + 1)

if n <= 6:
    print(n)
    exit(0)

for i in range(1, 7):
    dp[i] = i

for i in range(7, n + 1):
    for j in range(3, n + 1):
        if i - j < 0:
            break
        dp[i] = max((j - 1) * dp[i - j], dp[i])

print(dp[n])

---

Reference

• kibbomi.tistory.com/96