[백준] #11058 크리보드 - 파이썬

문제

크리보드는 kriii가 만든 신기한 키보드이다. 크리보드에는 버튼이 4개만 있으며, 하는 역할은 다음과 같다.

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

크리보드의 버튼을 총 N번 눌러서 화면에 출력된 A개수를 최대로하는 프로그램을 작성하시오.

입력

첫째 줄에 N(1 ≤ N ≤ 100)이 주어진다.

출력

크리보드의 버튼을 총 N번 눌러서 화면에 출력할 수 있는 A 개수의 최댓값을 출력한다.

예제 입력 1 

3

예제 출력 1 

3

예제 입력 2 

7

예제 출력 2 

9

---

복기

1. 패턴을 파악하기 너무 어렵다...ㅠㅠ

2. 복붙을 하려면 전체선택(Ctrl+A) -> 복사(Ctrl+C) -> 붙혀넣기(Ctrl+V) 이렇게 최소 3개의 클릭이 필요하다. 이 방법을 하려면 그냥 A를 출력할때보다 같거나 이득이어야 한다. 즉, 기존에 A가 최소 3개는 있어야 한다. 

3. 왜 loop를 6부터 시작하나면, N=5이면 A만 5번 누르는게 더 효과적이라 복붙이 오히려 손해여서이다. N>=6 일때부터 같거나 이득이다. 

4. N=6 이후에, 

dp[i] = max(2 * dp[i-3], 3 * dp[i-4], 4 * dp[i-5])

의 의미를 천천히 살펴보자.

2 * dp[i-3]는 i-3까지의 A의 입력이 있고, 이후 3개의 버튼을 사용한다. Ctrl-A(i-2) > Ctrl-C(i-1) > Ctrl+V(i). 이렇게 하면 화면에 있는 A의 개수가 2배가 된다. 

3 * dp[i-4]는 i-4까지 A를 만들어 놓고 Ctrl-A>Ctrl-C>Ctrl-V>Ctrl-V를 하면 A의 개수가 3배가 된다. 

i - 5     i - 4     i - 3     i - 2     i - 1     i
  ↓         ↓         ↓         ↓         ↓       ↓
[A A A] + [Ctrl-A] + [Ctrl-C] + [Ctrl-V] + [Ctrl-V] + [Ctrl-V]
          ↑ 만들어 놓은 A 복사         ↑ 붙여넣기 3번 → 4배

---

솔루션

n = int(input())
dp = [*range(0, n + 1)]  # 초기값: A만 누르는 경우

for i in range(6, n + 1):  # 최소 3번 복사-붙여넣기 하려면 6번 이상 필요
    dp[i] = max(
        2 * dp[i - 3],  # Ctrl-A, Ctrl-C, Ctrl-V 1번
        3 * dp[i - 4],  # Ctrl-A, Ctrl-C, Ctrl-V 2번
        4 * dp[i - 5],  # Ctrl-A, Ctrl-C, Ctrl-V 3번
    )

print(dp[n])