백준 11058번: 크리보드

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

문제 풀이

DP

$dp[i][j]$ = 버튼을 $i$번 누르고, 마지막에 누른 버튼이 $j$일 때 출력된 A개수의 최댓값

$dp[i][0] = max(dp[i-1][j])+1$ $(j \ge 0,$ $j \le 3)$

$dp[i][1] = max(dp[i-1][j])$ $(j \ge 0,$ $j \le 3)$

$dp[i][2] = dp[i-1][1]$

$dp[i][3] = max(dp[i-j][2] \times (j+1))$ $(j \ge 0,$ $j \le i)$

위의 점화식대로 테이블을 구하고 $dp[N][j]$ $(j \ge 0,$ $j \le 3)$의 최댓값을 출력하면 정답

풀이 설명

버튼 4개를 N번 눌러서 출력된 A의 개수의 최댓값을 구해본다고 생각하면 버튼 4개 중 하나를 N번 선택해 나열하는 순서쌍을 모두 확인해 그 때 출력되는 A의 개수를 확인해 최댓값을 구하는 방법이 있을것이다.

이 때 순서쌍을 마지막 버튼과 그 전까지로 나눈다면 이전까지 눌렸던 버튼에 의해 출력된 A의 개수에 마지막 버튼에 의해 추가로 출력되는 A의 개수를 합한 것이 현재 순서쌍에 의해 출력되는 A의 개수라는 것을 알 수 있다.

이로 인해 모든 순서쌍을 확인할 필요 없이 이전 버튼들에 의한 A의 개수의 최댓값에 현재 누른 버튼에 의해 추가로 출력되는 A의 개수의 값을 더하면 현재 버튼으로 만들 수 있는 A의 개수의 최댓값이 된다.

따라서 이전까지의 최댓값에 현재 버튼을 눌렀을 때의 최댓값을 더해 답을 구할 수 있지만, 버튼 4개를 봤을 때 첫 번째 버튼 A와 두 번째 버튼 CTRL-A는 이전에 어떤 버튼을 누르던 제 기능을 할 수 있지만, 세 번째 버튼 CTRL-C와 네 번째 버튼 CTRL-V는 각각 CTRL-A와 CTRL-V가 이전에 눌린적이 있어야 정상적으로 작동을 하기 때문에 이전까지의 최댓값도 어떤 버튼이 눌렸는지를 구분해야 한다.

그러므로 $dp[i][j]$ = 버튼을 $i$번 누르고, 마지막에 누른 버튼이 $j$일 때 출력된 A개수의 최댓값이라고 정의할 수 있고 점화식은

$dp[i][0] = max(dp[i-1][j])+1$ $(j \ge 0,$ $j \le 3)$

$dp[i][1] = max(dp[i-1][j])$ $(j \ge 0,$ $j \le 3)$

$dp[i][2] = dp[i-1][1]$

$dp[i][3] = max(dp[i-j][2] \times (j+1))$ $(j \ge 0,$ $j \le i)$

이렇게 나오게 된다.

먼저 마지막 버튼이 첫 번째 버튼일 경우는 이 버튼의 동작이 A를 한 개 출력하는 것이기 때문에 이전 버튼까지의 최댓값에 1을 추가하면 된다.

두 번째 버튼의 경우 현재까지 출력된 A를 선택하는 버튼이기 때문에 이전까지의 최댓값에서 변하지 않는다.

세 번째 버튼의 경우 선택되어있어야지만 복사를 할 수 있기 때문에 이전까지 선택되어있는 최댓값을 가져간다.

마지막으로 네 번째 버튼의 경우 복사되어있는 내용을 출력에 추가하는 버튼이므로, 세 번째 버튼에 의해 복사된 만큼 추가를 하는 것이니 복사를 언제 했는지가 중요하다.

만약 직전 버튼에서 복사를 했다면 현재 출력된 전체를 선택해 복사한 경우가 A의 개수를 가장 많이 복사했을 것이므로 복사했을 때의 최댓값만큼 복사를 할 수 있을 것이다. 따라서 이 때 저장된 최댓값의 두 배가 된다.

현재 버튼에서 두 번째 전에 복사를 했었다면 현재 붙여넣기를 하면 이 때 저장된 최댓값만큼 붙여넣을 수 있고, 이 때 출력된 A의 개수를 늘리는 방법은 첫 번째 버튼을 눌러 한 개 추가하는 방법과 네 번째 버튼을 눌러 복사한 A의 개수만큼 출력에 붙여넣는 방법밖에 없기 때문에 출력된 A의 개수를 더 많이 늘리는 방법은 복사를 했다면 복사한 A의 개수가 1개 이상일 것이므로 붙여넣는 방법이 개수를 더 많이 늘릴 수 있으니 직전 버튼도 붙여넣기를 했을 때가 최댓값이다. 그러므로 이 때는 복사를 했었을 때의 최댓값의 3배가 된다.

이 때 직전 버튼에 복사를 했으면 2배, 두 번째 전 버튼에 복사를 했으면 3배인 것을 확인했고, 세 번째 전 버튼에서 복사를 했을 때도 두 번째 전 버튼에 복사를 했을때와 마찬가지로 붙여넣기가 A의 개수를 더 많이 늘릴 수 있기 때문에 복사한 이후에 모두 붙여넣기를 해 복사한 최댓값의 4배가 된다. 따라서 j번째 전에 복사한 최댓값에 j + 1배한 값들 중 최댓값을 고르면 된다.

이렇게 구한 점화식에 따라 dp 테이블을 채우고 N 번째에 어떤 버튼을 눌렀을 때가 출력하는 A의 개수의 최댓값인지를 출력하면 정답이 나온다.

소스 코드

fun main(){
    val br = System.`in`.bufferedReader()
    val N = br.readLine().toInt()

    val dp = Array(N + 1){LongArray(4)}
    for(i in 1..N){
        var max = 0L
        for(j in 0..3){
            if(dp[i - 1][j] > max){
                max = dp[i - 1][j]
            }
        }
        dp[i][0] = max + 1 // press A
        dp[i][1] = max // CTRL + A
        dp[i][2] = dp[i - 1][1] // CTRL + C
        max = 0
        for(j in 1..i){
            if(dp[i - j][2] == 0L) break
            if(max < dp[i - j][2] * (j + 1)){
                max = dp[i - j][2] * (j + 1)
            }
        }
        dp[i][3] = max // CTRL + V
    }
    var answer = 0L
    for(j in 0..3){
        if(answer < dp[N][j]){
            answer = dp[N][j]
        }
    }
    println(answer)
}