백준 20365. 블로그2

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

20365번: 블로그2

 

 

1. 문제 설명

 

이때, 모든 문제를 원하는 색으로 칠할 때까지 필요한 작업 횟수의 최솟값을 출력하라

위 예시의 정답은 1~7번 문제를 파란색, 3번을 빨간색, 5번을 빨간색, 8번을 빨간색으로 순서대로 칠한다면 작업 횟수는 4번이다.

 

 

2. 접근법

 

처음에는 가장 많이 색을 칠해야 하는 것을 한번에 칠하고 그 이후에 각 문제를 하나씩 색칠해 가는 방식으로 풀었음

하지만, 문제 요구 사항 중 하나는 "연속된 임의의 문제를 선택하여 색칠한다"임

 

즉, 연속된 문제들을 한번에 색칠한다는 것을 생각하며 풀어나가야함

 

위 문제는 그리디로 풀 수 있음

가장 많이 칠해야 색깔을 구한뒤 해당 범위를 모두 그 색으로 색칠한 뒤

다른 색으로 색칠해야하는 부분들을 색칠해 나가면됨

 

 

 

3. 설계

 

- 연속된 부분을 하나로 간주하여 각 색깔을 몇번 색칠해야 하는지 구함

- 그 중에서 가장 많이 색칠해야하는 부분은 한번에 색칠

- 나머지 부분을 차례로 색칠해나감

 

 

4. 코드

 

import java.util.*;
import java.io.*;



public class Main {



    public static void main(String args[]) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        String line = br.readLine();

        int b = 0;
        int r = 0;

        if (line.charAt(0) == 'B') {
            b += 1;
        } else if (line.charAt(0) == 'R') {
            r += 1;
        }

        for (int i=1; i<n; i++) {
            if (line.charAt(i-1) != line.charAt(i)) {
                if (line.charAt(i) == 'B') {
                    b += 1;
                } else {
                    r += 1;
                }
            }
        }

        System.out.println(Math.min(b, r) + 1);

    }
}