백준 20365 - 블로그2 (자바 - 그리디)

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

20365번: 블로그2

 

* 문제 요약

블로그를 운영하는 일우는 매일 아침 풀고 싶은 문제를 미리 정해놓고 글을 올린다. 그리고 매일 밤 각각의 문제에 대하여 해결한 경우 파란색, 해결하지 못한 경우 빨간색으로 칠한다.

일우는 각 문제를 칠할 때 아래와 같은 과정을 한 번의 작업으로 수행한다.

1. 연속된 임의의 문제들을 선택한다.

2. 선택된 문제들을 전부 원하는 같은 색으로 칠한다.

 

예를 들어, 각 문제를 위와 같은 색으로 칠하려고 할 때, 1~2 번 문제를 파란색, 3번을 빨간색, 4번을 파란색, 5번을 빨간색, 6~7 번을 파란색, 8번을 빨간색으로 칠하는 작업을 순서대로 수행하면 6번의 작업을 거쳐야 한다.

하지만 1~7 번 문제를 파란색, 3번을 빨갠색, 5번을 빨간색, 8번을 빨간색 순서대로 칠한다면 작업횟수는 4번으로 가장 적다.

일우는 매일 500,000 문제까지 시도하기 때문에, 이 작업이 꽤나 귀찮아지기 시작했다. 그래서 가장 효율적인 방법으로 위 작업을 수행하기를 원한다. 일우를 도와 각 문제를 주어진 색으로 칠할 때 필요한 최소한의 작업횟수를 구하는 프로그램을 작성하라.

 

* 입력

첫째 줄에 색을 칠해야 하는 문제의 수 N (1 <= N <= 500,000) 이 주어진다.

둘째 줄에 N 개의 문자가 공백 없이 순서대로 주어진다. 각 문자는 i 번째 문자를 어떤 색으로 칠해야 하는지를 의미하며, R 은 빨간색, B 는 파란색을 나타낸다.

그외에 다른 문자는 주어지지 않는다. 

 

* 출력

첫째 줄에 일우가 주어진 모든 문제를 원하는 색으로 칠할 때까지 필요한 작업 횟수의 최솟값을 출력하라.

 

* 예시

 

* 해결 과정

문자열을 처음부터 끝까지 탐색하며 현재 색깔이 무엇인지에 따라 다음과 같은 조건을 수행한다.

1. 현재 탐색중인 색깔이 기존의 색깔과 같을 경우 건너뛴다.

2. 현재 탐색중인 색깔이 기존의 색깔과 다를 경우, 기존의 색깔의 상태를 변환하고 해당 색깔의 갯수를 1 증가시킨다.

문자열의 탐색이 끝나고 각 색깔의 갯수가 나올 경우, 색깔을 칠하는 작업횟수의 최솟값은 둘 중 갯수가 더 작은 색깔의 갯수 + 1 이다.

왜냐하면 갯수가 더 많은 색깔의 경우 처음에 전체적으로 모두 다 칠해준 다음 (1회), 갯수가 더 작은 색깔을 각 그룹별로 색칠(갯수가 더 작은 색깔의 갯수만큼 작업) 해주는 방식으로 작업을 수행하면 색깔을 칠하는 작업횟수의 최소에 가까운 근사값을 얻을 수 있기 때문이다.

 

* 코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

public class Main {
    public static void main(String[] args) throws NumberFormatException, IOException {
        new Main().solution();
    }

    private void solution() throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int size = Integer.parseInt(br.readLine());
        String str = br.readLine();

        int blueCount = 0;
        int redCount = 0;
        char currentColor = 'N';
        for (int i = 0; i < size; i++) {
            if (str.charAt(i) == 'B') {
                if (currentColor == 'B')
                    continue;
                else {
                    blueCount++;
                    currentColor = 'B';
                }
            } else if (str.charAt(i) == 'R') {
                if (currentColor == 'R')
                    continue;
                else {
                    redCount++;
                    currentColor = 'R';
                }
            }
        }

        bw.write((Math.min(redCount, blueCount) + 1) + "\n");
        bw.flush();
        bw.close();
        br.close();
    }
}

 

현재 상황에 최적의 해답을 선택한다. -> 현재 색깔이 어떤 색깔인지를 기준으로 색깔이 달라졌을 경우, 현재 색깔의 상태를 변화시키고 해당 색깔의 갯수에 1 을 더해준다.

선택된 해답이 조건을 만족하는지 검사한다. -> 파란색, 빨간색 각 색깔의 갯수가 모두 구해지지 않아서 둘 중 갯수가 더 작은 색깔을 특정할 수 없어 색깔을 칠하는 횟수의 최솟값을 구할 수 없는 경우, 반복문을 계속해서 수행한다.

 

위와 같은 과정을 통해 갯수가 더 작은 색깔의 갯수 + 1 의 결과값으로 색깔을 칠하는 횟수의 최소에 가까운 값을 얻을 수 있었으므로 그리디 알고리즘에 해당된다.