[BOJ/Silver 1] 백준 25215 타이핑(C++)

문제 링크

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

25215번: 타이핑

 

문제

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

• 알파벳 버튼을 누르면 소문자 또는 대문자 중 하나가 입력된다. 이때, 마름모 버튼이 활성화되어있다면 대문자, 아니라면 소문자가 입력된다. 마름모 버튼은 처음에 비활성화되어있다.
• 마름모 버튼은 한번 누를 때마다 활성화 및 비활성화 여부가 바뀐다.
• 별 버튼을 누르면 마지막으로 입력한 알파벳의 대소문자 여부가 바뀐다. 예를 들어 대문자가 마지막으로 입력되었을 경우 소문자로 바뀌고, 소문자가 마지막으로 입력되었을 경우 대문자로 바뀐다. 만약 마지막으로 입력한 알파벳이 없다면 작동하지 않는다.

 

민겸이는 사용할 수 있는 28개의 버튼을 이용해 어떤 문자열을 입력하려고 한다. 이때, 가능한 한 적은 횟수만큼 버튼을 누르고 싶다. 민겸이가 해당 문자열을 입력하기 위해 버튼을 최소 몇 번 눌러야 하는지 알려주자.

 

입력

입력은 한 줄로 주어진다.

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

 

출력

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

 

제한

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

 

예제 입력 1

iLoveINHA

예제 출력 1

11

 

I L ★ O V E ◆ I N H A 순으로 입력하면 버튼을 11번 누르고 입력할 수 있다.

10번 이하의 입력으로 이 문자열을 입력하는 방법은 없다.

예제 입력 2

ConquerThePlanet

예제 출력 2

19

 

알고리즘 분류

• 그리디 알고리즘

 

풀이

기본적으로 입력할 문자열의 길이만큼은 타이핑을 해야 한다.

키보드는 처음에 소문자인 상태이고, 일단 대문자가 처음으로 등장했다면 마름모든 별이든 간에 버튼을 1회 더 누른다.

대문자가 1번만 등장하고 바로 다시 소문자가 나타났다면 별 버튼을 1회 누른 것이 된다.

대문자가 연속으로 2번 이상 등장한 후 소문자가 등장했다면, 버튼을  1회 더 눌러야 한다. 그 다음 문자도 소문자라면 최종적으로 마름모 버튼을 2회 누른 것이 된다. 그 다음 문자가 대문자라면 최종적으로 마름모 버튼을 1회, 별 버튼을 1회 누른 것이 된다.

예를 들어 다음 문자열을 보자.

afKjAOnnMjjjEQeAC

 

이 문자열의 마지막 5개의 문자는 대문자가 2회 연속으로 등장하고, 중간에 소문자가 1회 등장한 후 마지막으로 다시 대문자가 2회 연속으로 등장한다.

그런데 일반적으로 생각한다면 먼저 마름모 버튼을 2회 눌러서 먼저 등장한 2개의 대문자를 입력하고, 소문자를 1회 입력하고 다시 마름모 버튼을 눌러 마지막 2개의 대문자를 입력하게 되는데 이렇게 되면 버튼을 3회를 추가로 눌러야 한다.

그러나 소문자가 한 번만 등장할 때에만 별 버튼을 누른다면 최종적으로는 2회의 버튼을 눌러 버튼을 누르는 횟수를 1회 줄일 수 있게 된다.

 

코드

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#define FASTIO cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);

using namespace std;
string S;
int Cnt_Upper;
int Answer;

void input() {
    cin >> S;
}

void settings() {
    Answer = (int)S.length();
    for (int i = 0; i < (int)S.size(); i++) {
        char Now = S[i];
        if ((Now >= 'A') && (Now <= 'Z')) {
            if (Cnt_Upper == 0) {
                Answer++;
            }
            Cnt_Upper++;
        }
        else {
            if (Cnt_Upper > 1) {
                Answer++;
                if (i < ((int)S.size() - 1)) {
                    char Next = S[i + 1];
                    if ((Next >= 'a') && (Next <= 'z')) {
                        Cnt_Upper = 0;
                    }
                }
            }
            else if (Cnt_Upper == 1) {
                Cnt_Upper = 0;
            }
        }
    }
}

void find_Answer() {
    cout << Answer << "\n";
}

int main() {
    FASTIO
    input();
    settings();
    find_Answer();

    return 0;
}