1. 문제
https://www.acmicpc.net/problem/5577
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);
}
}
'코딩문제풀이 > Baekjoon' 카테고리의 다른 글
[Java] 백준 1613번 : 역사 (0) | 2022.04.10 |
---|---|
[Java] 백준 11054번 : 가장 긴 바이토닉 부분 수열 (0) | 2022.04.10 |
[Java] 백준 19236번 : 청소년 상어 (0) | 2022.04.07 |
[Java] 백준 17471번 : 게리맨더링 (0) | 2022.04.06 |
[Java] 백준 2239번 : 스도쿠 (0) | 2022.04.06 |