[백준] 11058 크리보드

문제 링크

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

사용 알고리즘

• DP

풀이

dp 배열의 각 인덱스를 현재 버튼을 i개 눌렀을 때 화면에 출력된 A의 최대 개수로 가정한다.

▶︎ `dp[i] = i번 버튼을 눌렀을 때 화면에 출력된 A의 최대 개수`

 

dp 배열의 초기값으로는 단순이 A만 눌렀을 때 화면에 출력된 A의 개수로 설정해두고,

각 위치에서 Ctrl-A, Ctrl-C, Ctrl-V를 했을 경우(= `i + 2`) 나올 수 있는 A의 개수로 dp 배열을 갱신해주면 된다.

코드

import sys, os, io, atexit

input = lambda: sys.stdin.readline().rstrip('\r\n')
stdout = io.BytesIO()
sys.stdout.write = lambda s: stdout.write(s.encode("ascii"))
atexit.register(lambda: os.write(1, stdout.getvalue()))

n = int(input())

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