[Python] 백준 11058번: 크리보드

# 문제 내용

백준 11058번: 크리보드

11058번: 크리보드

 

# 알고리즘 분류

• 다이나믹 프로그래밍

 

# 풀이

import sys
input = sys.stdin.readline

# 버튼 1 : 화면에 A를 출력한다.
# 버튼 2 : Ctrl-A: 화면을 전체 선택한다
# 버튼 3 : Ctrl-C: 전체 선택한 내용을 버퍼에 복사한다
# 버튼 4 : Ctrl-V: 버퍼가 비어있지 않은 경우에는 화면에 출력된 문자열의 바로 뒤에 버퍼의 내용을 붙여넣는다.

# 버튼 클릭 횟수
n = int(input())

# 버튼 횟수에 따른 DP - 버튼 1만 눌렀을 때로 초기화 
dp = [i for i in range(0, n+1)]
  
# 1 ~ 6까지는 복사보다 A입력이 더 많은 수 출력 가능  
# 7부터는 복사가 더 많은 A 출력할 수 있음
for i in range(7, n+1):
  # 현재보다 3번 전의 값을 1번 복사 하는 경우
  # 현재보다 4번 전의 값을 2번 복사 붙여넣기 하는 경우
  # 현재보다 5번 전의 값을 3번 복사 붙여넣기 하는 경우
  dp[i] = max(dp[i-3] * 2, dp[i-4] * 3, dp[i-5] * 4)
  
print(max(dp))

 

# References

https://dirmathfl.tistory.com/193

백준: 11058 크리보드