[백준 / Java] 25215. 타이핑

문제 정보

• 태그: 그리디, DP
• 난이도: 실버 1

문제

민겸이는 영어 소문자와 대문자로 이루어진 문자열을 타이핑하기로 했다. 민겸이가 사용할 수 있는 버튼은 26개의 영어 알파벳 버튼과 마름모(◆) 버튼, 별(★) 버튼이다. 각 버튼은 아래와 같이 작동한다.

알파벳 버튼을 누르면 소문자 또는 대문자 중 하나가 입력된다. 이때, 마름모 버튼이 활성화되어있다면 대문자, 아니라면 소문자가 입력된다. 마름모 버튼은 처음에 비활성화되어있다.
마름모 버튼은 한번 누를 때마다 활성화 및 비활성화 여부가 바뀐다.
별 버튼을 누르면 마지막으로 입력한 알파벳의 대소문자 여부가 바뀐다. 예를 들어 대문자가 마지막으로 입력되었을 경우 소문자로 바뀌고, 소문자가 마지막으로 입력되었을 경우 대문자로 바뀐다. 만약 마지막으로 입력한 알파벳이 없다면 작동하지 않는다.
민겸이는 사용할 수 있는 28개의 버튼을 이용해 어떤 문자열을 입력하려고 한다. 이때, 가능한 한 적은 횟수만큼 버튼을 누르고 싶다. 민겸이가 해당 문자열을 입력하기 위해 버튼을 최소 몇 번 눌러야 하는지 알려주자.

입력

입력은 한 줄로 주어진다.

첫 번째 줄에 민겸이가 타이핑할 문자열이 주어진다.

출력

민겸이가 해당 문자열을 입력하기 위해 버튼을 최소 몇 번 눌러야 하는지 출력한다.

제한

• 1 ≤ 문자열의 길이 ≤ 3,000
• 주어지는 문자열은 알파벳 대소문자로만 이루어져 있다.

풀이

태그를 보니 그리디 풀이도 있는 것 같다. 나는 dp로 해결하였다.
우선 인덱스 i번째 알파벳을 누르기까지의 최소 타이핑 수를 저장하는 dp 배열을 아래 그림과 같이 선언해줬다.

dp = new int[2][s.length()+1]; // 여기서 s는 입력 문자열

문자열 길이보다 열을 하나 더 길게 선언한 이유는 0열은 문자열을 타이핑하기 전 마름모 버튼을 누르고 시작할지 안누르고 시작할지를 결정하는 칸으로 쓰기 위해서이다.
그림에서 보다 싶이 0행은 마름모가 비활성 돼있는 상태, 1행은 마름모가 활성 돼있는 상태이다.

인덱스를 보기 편하게 하기 위해 아래 코드처럼 입력 스트링 맨 앞에 공백을 하나 넣어주었다. 이렇게 하면 첫번째 알파벳의 인덱스가 1이 되게 된다.
그리고 dp[0][0] = 0, dp[1][0] = 1로 초기화 해주었다. (처음 시작할 때 마름모는 비활성 상태이기에, 비활성을 유지하려면 아무것도 안누르면 되고, 활성으로 바꾸려면 한번 눌러야 하기 때문이다.)

그리고 스트링의 문자들을 하나하나씩 보며 dp 배열을 채워나가면 된다. i번째 문자를 칠 때까지 몇번을 쳐야 최소인지를 따지기 위해서는 두 가지 케이스로 나누어서 생각을 해야한다. (i) i번째 문자가 소문자일때, (ii) i번째 문자가 대문자 일때.

위의 점화식으로 i번째 문자가 소문자인 상황을 생각해보자.
우선 dp 배열을 0행은 마름모 비활, 1행은 마름모 활성화인 상태로 나누어 놓았으므로 두 상황을 나누어 생각해보자.

• 비활성화 상황: dp[0][i]
  i번째 문자를 치고나서 마름모가 비활되는 상황은 두 가지 이다. 첫번째는 원래 비활성화 된 상태에서 그냥 한번 타이핑하는 경우(타이핑 1회), 두번째는 원래 마름모가 활성되어있는 상황에서 마름모를 한번 눌러 비활성화 시킨 후 문자를 타이핑하는 경우(타이핑 2회).
  따라서 점화식은 위와 같다.

• 활성화 상황: dp[1][i]
  i번째 문자를 치고나서 마름모가 활성화되는 상황은 한가지만 고려해주면 된다. 원래 활성화였던 상황에서 일단 대문자를 누른 다음 별표로 바꾸어주는 경우 (타이핑 2회).
  따라서 점화식은 위와 같다.
  마름모 버튼을 눌러서 비활성화 시킨 후 소문자를 누르고 다시 활성화 시키는 경우 같은 것(타이핑 3회)은 고려해주지 않아도 된다. 어차피 다음 문자열이 대문자라면 그 때 마름모 비활 -> 활성화 해주는 경우를 고려해주기 때문에 굳이 여기서 다시 활성화해줄 필요가 없는 것이다.

대문자인 경우는 사실 소문자인 경우와 같은 논리이기 때문에 설명을 생략하려고 한다..!ㅎㅎ
그래도 점화식은 아래 전체 코드에서 확인할 수 있다.

마지막으로 dp[0][문자열길이], dp[1][문자열길이] 중 더 작은 값을 출력해주면 답이 된다.

전체 코드

// 백준 25215. 타이핑 
import java.io.*;
import java.util.*;

class Main {
    static String s;
    static int dp[][];
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        s = br.readLine().trim();
        dp = new int[2][s.length()+1];

        s = " " + s; // 인덱스를 맞춰주기 위해 (문자열의 시작을 1부터)

        dp[0][0] = 0; // 0행 -> 마름모 비활성화
        dp[1][0] = 1; // 1행 -> 마름모 활성화

        for(int i=1; i<s.length(); ++i) {
            if(s.charAt(i) >= 'a' && s.charAt(i) <= 'z') { // 소문자이면
                dp[0][i] = Math.min(dp[0][i-1] + 1, dp[1][i-1]+2);
                dp[1][i] = dp[1][i-1] + 2; // 활성화를 유지
            } else { // 대문자이면
                dp[1][i] = Math.min(dp[1][i-1] + 1, dp[0][i-1]+2);
                dp[0][i] = dp[0][i-1] + 2; // 비활유지
            }
        }

        int ans = Math.min(dp[0][s.length()-1], dp[1][s.length()-1]);

        System.out.println(ans);
    }

}