[JAVA] BOJ(백준) - 블로그2 - 20365

문제내용

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

출력

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

---

문제풀이

풀이는 간단하지만 이런류(그리디)의 문제는 아이디어를 떠올리는게 생각보다 쉽지않다. 그래도 이문제는 쉬운축에 속한다.

 

최소한의 작업으로 모든 색을 알맞게 칠하기 위해서

전체를 B or R 로 칠하고 나머지 색을 채워주면된다.

즉, 전체를 B로 칠했다면 R그룹의 개수 + 1

전체를 R로 칠했다면 B그룹의 개수 + 1

을 해주면된다. (여기서 +1은 전체를 칠할때 작업 한번을 의미)

 

---

코드

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));
		int n = Integer.parseInt(br.readLine());
		String str = br.readLine();
		
		char[] arr = str.toCharArray();
		int a=1,b=0;//색별로 변수만듦. a는 첫번째로 나오는 색이기 때문에 1로 시작한다.
		char color = arr[0]; //색
		boolean flag = false; //이전그룹과 다른 그룹인지 구분하기 위해 사용.
		for(int i=1; i<n; i++) {
			//이전과 다른 색이 나왔을대 flag 기준으로 그룹을 구분하고, 알맞은 그룹에 +1을 시켜준다.
			//그리고 이전색에서 현재색으로 바꿔줌.
			if(arr[i]!=color && !flag) {
				b++;
				flag = true;
				color = arr[i];
			}else if(arr[i]!=color && flag) {
				a++;
				flag = false;
				color = arr[i];
			}
		}
		
		int min = Math.min(a, b) + 1;//최소그룹 + 1
		System.out.println(min);
	}
}

 

---

마치며

최근데 코딩테스트에서 그리디 관련문제가 2개나 나왔다. 근데 이전에 그리디문제를 푼경험이 부족해서 애먹었던 기억이 있다. 그래서 당분간은 블로그 포스팅외에도 그리디 문제를 중점적으로 연습할 생각이다.