20365번 : 블로그2

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

20365번: 블로그2

 

문제

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

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는 파란색을 나타낸다. 그 외에 다른 문자는 주어지지 않는다.

 

출력

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

 

---

소스코드

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        br.readLine();
        String[] arr = br.readLine().split("");

        int count1 = 0;
        String s = "B";
        for (int i = 0; i < arr.length; i++) {
            if(arr[i].equals("R") && s.equals("B")) count1 += 1;
            s = arr[i];
        }

        int count2 = 0;
        s = "R";
        for (int i = 0; i < arr.length; i++) {
            if(arr[i].equals("B") && s.equals("R")) count2 += 1;
            s = arr[i];
        }
        
        if(count1 > count2) System.out.println(count2 + 1);
        else System.out.println(count1 + 1);
    }
}

 

해결방법

가장 효율적인 방법으로 색을 칠하는 방법은 "R" 또는 "B"로 전체를 칠한 뒤 남은 색들을 칠하는 것이다.

전체를 "R"로 칠한다면 "B" 부분만 칠해주면 되므로 ( [n-1] = "R"  &&  [n] = "B") 인 경우를 세주면 된다.

마찬가지로 전체를 "B"로 칠하는 경우도 위와 동일하다.

 

두 경우를 세준 뒤 더 작은 값을 가지는 횟수가 최소 작업 횟수이다.

주의할 점으로는 처음에 전체를 "R" 또는 "B"로 칠하는 경우를 한 세었으므로 마지막에 더해줘야 한다.