크리보드

문제해석

4가지의 동작이 있다.

1. 화면에 A를 출력한다.
2. 화면을 전체 선택한다.
3. 선택한 내용을 버퍼에 복사한다.
4. 버퍼의 내용을 현재 화면 맨 끝에 붙여넣는다.

결국은 A를 최대 몇 개 출력할 수 있는지를 찾아내면 되는 문제다.

1, 2, 3, 4 각 버튼을 A, S, C, V라고 하자. 그러면 A, SCV, SCVV, SCVVV... 동작들의 조합으로 이루어져 있음을 알 수 있다. 즉, 최소한 SCV는 같이 눌려야 한다.

각 N에 대하여 어떤 값들이 올 수 있는지 생각해본다면

1. 단순히 최대인 N-1값에 1을 더한 값이 올 수 있다. 즉, 버튼 A를 누르는 경우
2. 최소한 SCV는 같이 눌러야 하므로, N-3값에 SCV를 눌러 값을 구성할 수 있다.
3. SCVV와 같이 누를 수 있으므로, N-4값에 SCVV를 눌러 값을 구성할 수 있다.
4. SCVVV...와 같이 누를 수 있으므로, N-k값에 SCVVV...를 눌러 값을 구성할 수 있다.

우리가 구하고자 하는것은 최댓값이므로, 각 N에 대해 최댓값을 저장하고 N-k값에 위와 같은 버튼의 조합을 눌렀을 때 최댓값을 구성하는 전형적인 DP방식으로 답을 구하면 될 것 같다. 이를 cache[N]이라고 하자.

N-1에 1을 더하는 경우는 별다른 증명이 필요 없이 직관적으로 알 수 있다. 어차피 버튼은 1번만 누르거나 최소 3개 이상을 같이 눌러야 하기 때문에, 의심의 여지 없이 최대인 N-1에 1을 더하는 값이 최댓값이다.

SCV를 같이 눌러야 하는 경우, 즉 cache[N-k](k >= 3)값에 대하여 이 값이 최대가 아닌 상태에서도 최댓값이 나올 수 있다면 전형적인 DP방식으로 풀었을 때 답을 구할 수 없을 수도 있다. 최댓값에 대해 SCVV...를 눌러도 최댓값을 구할 수 있음을 증명해보자.

증명

N-k(k >= 3)이 최댓값이 아닌 값 cache[N-k]에 SCVV...버튼을 눌러서 최댓값이 나올 수 있다고 가정해보자. 우리는 버튼을 SCV SCVV... 와 같이 누르는데, 이 때 SC의 동작은 현재까지 출력된 A의 갯수를 버퍼에 복사하는 행위고 V를 눌렀을 때 붙여넣기가 되는 것이다.

따라서, cache[N-k]가 값이 크면 클수록 V에 의해 붙여넣기 되는 값이 커지므로 cache[N-k]는 최댓값이어도 답을 구할 수 있다.

답

package main

import "fmt"

func main() {
	var cache [101]int

    // 1 ~ 6까지의 초깃값
	for n := 1; n <= 6; n++ {
		cache[n] = n
	}

	var N int
	fmt.Scanf("%d", &N)

	for cnt := 7; cnt <= N; cnt++ {
        // 이전값에 +1 더하는 경우
        // 사실 이 코드는 필요가 없다. N >= 7 이후에는 A를 눌러서 최댓값이 구성되는 경우는
        // 없기 때문이다.
        // Go의 경우 변수를 초기화하면 해당 타입의 기본값으로 초기화 되므로 상관없지만
        // 다른 언어의 경우 값의 초기화를 해줘야 될 수도 있다.
		cache[cnt] = cache[cnt-1] + 1

        // cnt에서의 최댓값은
        // SCV를 누르기 이전인 cache[cnt-3]의 값을 버퍼로 복사하는 것부터 시작하므로
        // before는 3부터 시작한다.
		for before := 3; before <= cnt; before++ {
            // cnt-before에서 프린트 된 값의 갯수에 V를 누른 횟수만큼 곱하면 된다.
            printed := cache[cnt-before]
            buf := cache[cnt-before]
            vCount := before-2
          
            cache[cnt] = max(cache[cnt], printed + (buf*vCount))
			
            // 위를 정리하면 아래와 같이 쓸 수 있다.
            // cache[cnt] = max(cache[cnt], cache[cnt-before]*(before-1))
		}
	}

	fmt.Println(cache[N])
}

func max(a, b int) int {
	if a > b {
		return a
	}

	return b
}