[JAVA] 백준 17615번 : 볼 모으기(한국정보올림피아드/KOI 2019 2차대회/초등부)

문제

그리디 문제이다.

 

해결 방안

처음에 R과 B의 갯수를 각각 세어서 rCnt, bCnt에 저장해준다.

그리디 문제로 볼을 이동하는 4가지 방법 중 최소 이동횟수를 구하면 된다.

1. R공을 모두 왼쪽으로 이동
문제의 그림1을 볼때 RRRRBBBB로 나열하기 위해서는 첫번째 R을 제외하고는 다 옮겨줘야 한다.
따라서 왼쪽에 R이 계속 있을경우 cnt를 세어준다음 Rcnt-cnt는 이동해야하는 R공의 갯수가 된다.
ex) RBBBRBRRR인 경우 첫번째 R이 있으므로 cnt = 1이된다. 따라서 Rcnt(5)-cnt(1)=4가 되고 실제로 왼쪽으로 이동해야하는 R공의 갯수가 된다.

2. R공을 모두 오른쪽으로 이동

3. B공을 모두 왼쪽으로 이동

4. B공을 모두 오른쪽으로 이동

2,3,4번도 뒤에서부터 세야되나 B공을 세야되나에 따라 각각 코드가 조금씩 달라지는거 외에는 같은 원리이다.
자세한 것은 코드를 보면 충분히 이해 가능하다.

 

코드

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

// 한국정보올림피아드
// KOI 2019 2차대회 초등부
// 볼 모으기
public class Main {

	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		String colors = br.readLine();
		int result = N;
		int rCnt = 0;
		int bCnt = 0;
		
		for(int i=0; i<N; i++) {
			if(colors.charAt(i)=='R') 
				rCnt ++;
			else
				bCnt ++;
		}
		
		int cnt = 0;
		// 4가지 경우
		// 1. R만 움직여서 RRRBBB(R을 다 왼쪽으로)
		for(int i=0; i<N; i++) {
			if(colors.charAt(i)=='R')
				cnt++;
			else
				break;
		}
		result = Math.min(result, rCnt-cnt);
		
		// 2. R만 움직여서 BBBRRR
		cnt = 0;
		for(int i=N-1; i>=0; i--) {
			if(colors.charAt(i)=='R')
				cnt++;
			else
				break;
		}
		
		result = Math.min(result, rCnt-cnt);
		
		// 3. B만 움직여서 BBBRRR
		cnt = 0;
		for(int i=0; i<N; i++) {
			if(colors.charAt(i)=='B')
				cnt++;
			else
				break;
		}
		result = Math.min(result, bCnt-cnt);
		
		// 4. B만 움직여서RRRBBB
		cnt = 0;
		for(int i=N-1; i>=0; i--) {
			if(colors.charAt(i)=='B')
				cnt++;
			else
				break;
		}
		
		result = Math.min(result, bCnt-cnt);
		
		System.out.println(result);
		
	}

}