[Java] 백준 5577번 : RBY팡!

1. 문제

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

5577번: RBY팡!

 

 

 

2. 풀이과정

1. 입력을 받으면서 같은 수 끼리 이어진 개수를 2차원 배열 (값, 개수)로 기록한다.

ex) 1113221 => {{1, 3}, {3, 1}, {2, 2}, {1, 1}}

 

2. 개수를 센 배열을 순차적으로 접근하면서 simulation을 한다.

최소로 하기 위해서는 같은 색이 이어진 곳 중간을 굳이 다른 색으로 바꿀 필요가 없다. 따라서, 지금 접근한 공의 끝 쪽이 자신의 위쪽과 색을 같게하거나, 밑쪽과 색을 같게하는 경우를 고려했다.

이를 자신의 개수를 -1하고, 자신의 위의 것 or 밑의 것 개수를 +1해주는 방식으로 처리해주었다.

 

3. 어떤 색으로 바꿀지 결정했으니, 터트려본다.

색을 바꿨을 때, 결과는 크게 두 경우로 나눠볼 수 있다.

1) 다른 색으로 바꿨지만, 현재 공이 아직 남은 경우

2) 다른 색으로 바꾸면서, 현재 공은 0개가 되는 경우 = 터트린 것과 동일한 효과

 

여기서 자신이 아직 남았고 && 2단계에서 더해준 곳의 개수가 4이상이면 터트리고 시작한다.

4미만이면, 변화없으니 stop해도 된다.

 

그 후, 터트려서 인접해진 up과 down의 색을 비교해서 같으면 합치고, 합친 값이 4이상이면 계속 진행한다.

아닌 경우, 바로 종료한다.

 

import java.io.*;

public class Boj5577 {
	static int size, arr[][], max;
	
	public static void go(int ball) {
		arr[ball][1]--;
		//위로 추가
		if(0 < ball) {
			arr[ball-1][1]++;
			if(arr[ball][1]==0) {
				max = Math.max(max, simulation(ball-1, ball+1));
			}
			else {
				max = Math.max(max, simulation(ball-1, ball));
			}
			arr[ball-1][1]--;
		}
		//아래로 추가
		if(ball < size-1) {
			arr[ball+1][1]++;
			if(arr[ball][1]==0) {
				max = Math.max(max, simulation(ball-1, ball+1));
			}
			else {
				max = Math.max(max, simulation(ball, ball+1));
			}
			arr[ball+1][1]--;
		}
		arr[ball][1]++;
	}
	
	public static int simulation(int up, int down) {
		int result = 0;//터트린 공의 수
		//변경한 공의 위치의 색깔 수가 0이면 넘어가도록 함
		if(0<=up && down-up==1 && arr[up][1] >= 4) {
			result+=arr[up][1];
			up--;
		}
		else if(down<size && down-up==1 && arr[down][1] >= 4) {
			result+=arr[down][1];
			down++;
		}
		
		while(0<=up && down<size) {
			if(arr[up][0] != arr[down][0]) break;//인접해진 두 색깔이 다르면
			if(arr[up][1] + arr[down][1] < 4) break;//인접해진 두 값의 합이 4미만
			
			result+=arr[down][1]+arr[up][1];
			up--;
			down++;
		}
		return result;
	}

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		arr = new int[N][2];
		
		int idx = 0;
		arr[0][0] = Integer.parseInt(br.readLine());
		arr[0][1] = 1;
		for(int i=1;i<N;i++) {
			int n = Integer.parseInt(br.readLine());
			if(arr[idx][0] == n) {
				arr[idx][1]++;
			}
			else {
				arr[++idx][0] = n;
				arr[idx][1] = 1;
			}
		}
		size = idx+1;
		
		for(int i=0;i<size;i++) {
			go(i);
		}
		System.out.println(N-max);
	}
}