백준 25215번: 타이핑

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

문제 풀이

DP

s = 최종적으로 입력되어야 하는 문자열

dp[i][j] = i번째 문자를 입력할 때 마름모가 활성화 또는 비활성화 되어있을 때 누르는 버튼의 최소 횟수

마름모가 활성화 상태라면 알파벳 입력할때 대문자로 입력됨

별 버튼을 누르면 마지막 문자를 대문자에서 소문자, 소문자에서 대문자로 변환함

따라서 마름모가 활성화 되어 있는지 여부에 따라 현재 소문자, 대문자 입력하는데 드는 버튼 횟수가 다름

그러므로 dp[i][0]을 i번째 문자를 입력할 때 마름모가 비활성화 되어있을 때 누르는 버튼의 최소 횟수, dp[i][1]을 i번째 문자를 입력할 때 마름모가 활성화 되어있을 때 누르는 버튼의 최소 횟수로 정의함

처음 상태가 마름모가 비활성화 상태라고 했으므로 dp[0][0]을 0, dp[0][1]을 1로 초기화해야 함

그 이후에 문자열에서 문자를 하나씩 확인하면서 현재 입력해야 하는 문자가 대문자인지 판단함

대문자가 입력된 이후에 마름모가 비활성화된 상태라면 소문자로 입력해 별 버튼을 눌러 대문자로 변환하는 방법이나 마름모가 활성화된 상태에서 대문자로 입력한 이후에 마름모 버튼을 눌러 비활성화하는 방법이 있음

이 상태의 버튼 누르는 최소 횟수는 두 상황 다 버튼을 두번 누르고 이전 상태에서 가져오므로 dp[i - 1][0] + 2, dp[i - 1][1] + 2임

대문자가 입력된 이후에 마름모가 활성화된 상태, 소문자가 입력된 이후에 마름모가 활성화, 비활성화된 상태도 모두 따져서 dp 배열을 채우면 dp[s.length][0]이 문자열 s를 입력한 이후 마름모가 비활성화 되었을 때 누르는 버튼의 최소 횟수, dp[s.length][1]이 문자열 s를 입력한 이후 마름모가 활성회 되었을 때 누르는 버튼의 최소 횟수이므로 둘을 비교해 최솟값을 출력하면 정답

풀이 설명

영어 소문자와 대문자로 이루어진 문자열이 주어진다. 그 문자열을 26개의 알파벳과 별, 마름모 버튼을 이용해 만드려고 하는데 별은 Shift, 마름모는 Caps Lock과 같은 기능을 한다고 할때 버튼을 최소 몇번 눌러서 문자열을 완성할 수 있는지 구하는 문제이다.

매 글자마다 마름모 버튼이 활성화 되어있는지에 따라 현재 누르는 알파벳이 소문자인지, 대문자인지 구별되고 이전에 마름모가 활성화 되어있는지에 따라 현재 마름모를 활성화 또는 비활성화해서 대문자 또는 소문자를 입력할 수 있기 때문에 DP로 문제를 풀 수 있다.

또한 별 버튼을 누르는 것도 마름모가 활성화되어있는지 여부에 따라 소문자 또는 대문자로 변형시키는 것이 다르기 때문에 이 상태도 같이 고려하면서 누르는 버튼의 횟수를 셀 수 있다.

이를 따라 문제를 풀기 위해 문자열 s가 있다고 하면 s의 i번째 문자를 입력하고 난 이후 마름모가 비활성, 활성화되어 있을 때 버튼이 눌린 최소 횟수를 dp[i][0], dp[i][1]로 정의한다.

그렇게 되면 현재 문자를 입력한 이후 비활성화된 상태 dp[i][0]을 확인할 때 확인해야 하는 것이 현재 문자가 소문자, 대문자인지 여부와 이전 상태에 마름모가 활성화되어있는지 여부이므로 4가지 상태를 확인해야 하고 dp[i][1]도 마찬가지로 4가지 상태를 확인해야 한다.

먼저 dp[i][0]부터 확인하기 위해 현재 입력할 문자가 대문자일 경우를 먼저 생각하면 이전에 마름모가 비활성화 상태였다면 문자를 소문자로 입력하고 별 버튼을 누르는 횟수 dp[i - 1][0] + 2와 이전에 마름모가 활성화 상태여서 문자를 대문자로 입력하고 마름모 버튼을 눌러 비활성화 상태로 바꾸는 dp[i - 1][1] + 2를 비교해 최솟값을 저장하면 된다.

또한 문자가 소문자일 경우 이전에 마름모가 비활성화 상태였다면 바로 문자를 소문자로 입력할 수 있으므로 dp[i - 1][0] + 1와 이전에 마름모가 활성화 상태였다면 마름모 버튼을 눌러 마름모를 비활성화 상태로 바꾸고 문자를 입력하는 경우 dp[i - 1][1] + 2를 비교해 최솟값을 저장하면 된다.

마찬가지로 dp[i][1]을 구하는 법도 대문자부터 확인하면 이전에 마름모가 비활성화 되어있을 때는 마름모 버튼을 눌러 활성화시키고 대문자를 입력해야 하므로 dp[i - 1][0] + 2와 이전에 마름모가 활성화되어 있었다면 바로 문자를 대문자로 입력하면 되므로 dp[i - 1][1] + 1을 비교해 최솟값을 저장하면 된다.

소문자일 경우에는 이전에 마름모가 비활성화 되어있다면 소문자를 입력하고 마름모 버튼을 눌러 활성화해야 하므로 dp[i - 1][0] + 2와 이전에 마름모가 활성화 상태라면 대문자를 입력하고 별 버튼을 눌러 소문자로 바꾸어야 하므로 dp[i - 1][1] + 2를 비교해 최솟값을 저장하면 된다.

그렇게 첫 문자부터 맨 마지막 문자까지 확인하며 dp배열을 채우면 dp[s.length][0]이 마지막 문자까지 입력하고 난 이후에 마름모가 비활성화 되어 있는 상태의 버튼을 누르는 최솟값, dp[s.length][1]이 마지막 문자까지 입력하고 난 이후에 마름모가 활성화 되어 있는 상태의 버튼을 누르는 최솟값이므로 둘 중 최솟값을 출력하면 정답이 된다.

소스 코드

fun main() = System.`in`.bufferedReader().run {
    val s = readLine()
    val dp = Array(s.length + 1){ IntArray(2) }
    dp[0][1] = 1
    for(i in 1..s.length){
        if(s[i - 1].isUpperCase()){
            dp[i][0] = minOf(dp[i - 1][0] + 2, dp[i - 1][1] + 2)
            dp[i][1] = minOf(dp[i - 1][0] + 2, dp[i - 1][1] + 1)
        } else {
            dp[i][0] = minOf(dp[i - 1][0] + 1, dp[i - 1][1] + 2)
            dp[i][1] = minOf(dp[i - 1][0] + 2, dp[i - 1][1] + 2)
        }
    }
    println(dp[s.length].min())
}