[백준 / BOJ] 11912번 : 격자 보존하기

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

11912번: 격자 보존하기

 

11912번 : 격자 보존하기 [그리디 알고리즘, 정렬]

 

어떤 격자가 말에게 더러워지지 않는 경우는 두 가지를 생각할 수 있다.

 

1. 칸막이를 한 개 사용해야 하는 경우 : 시작 ~ 첫 번째 말 / 마지막 말 ~ 끝

2. 칸막이를 두 개 사용해야 하는 경우 : 말과 말 사이

 

따라서 해당 두 가지 경우를 따로 저장했다. 

int[] one = new int[2]; // 칸막이 하나만으로 보호할 수 있는 배열
one[0] = horse[0]; // 시작 ~ 첫번째 말 사이의 격자 개수
one[1] = N - 1 - horse[K-1]; // 마지막 말 ~ 끝 사이의 격자 개수

List<Integer> list = new ArrayList<>(); // 말과 말 사이의 격자 개수를 넣을 리스트
for (int i = 1; i < K; i++) {
    int diff = horse[i] - horse[i-1] - 1; // 말과 말 사이의 격자 개수
    if(diff != 0) list.add(diff);
}

먼저 말과 말 사이에 칸막이를 놓을 때 최대한 많은 격자를 보존할 수 있는 경우를 찾는다.

말과 말 사이 격자를 보존할 때는 다른 어느 곳에 칸막이를 두었는지와 상관 없이, 무조건 칸막이 두 개가 더 필요하다. 즉, 어차피 같은 개수의 칸막이를 사용할 것이라면 그 사이의 격자 개수가 많은 곳을 골라야 한다. 이에 따라 말과 말 사이 격자 개수 리스트를 정렬한 뒤, 칸막이 개수를 다 사용할 때까지 더해 주었다.

list.sort(null); // 말과 말 사이의 격자 개수 리스트를 정렬했다. 

int d = 0; // 현재까지 사용한 칸막이 개수
int max = 0; // 현재까지 보존한 격자 개수
int M = list.size(); 
int stop = M; // 칸막이를 다 사용하고 멈춘 순서

for (int i = M - 1; i >= 0; i--) { // sort는 오름차순이므로 끝에서부터 돌린다.
    int cur = list.get(i);
    if(d + 2 <= D) { // 칸막이를 두 개 더 사용할 수 있는지 확인
        d += 2; // 칸막이 두 개 사용
        max += cur; // 보존할 수 있는 격자 개수를 더해준다.
    } else {
        stop = i; // 칸막이를 두 개 더 사용할 수 없다면 해당 위치를 저장하고 나간다.
        break;
    }
}

코드가 조금 난잡하지만, 결국 stop + 1번째까지의 격자 리스트를 더해준 것이다.

 

이제 양 끝쪽 격자까지 고려해줄 때가 되었다.

 

1. 남은 칸막이가 2개 이상이다 : 이 경우에는 아무 검증 없이 양 끝쪽 격자들을 보호해주면 된다.

 

2. 남은 칸막이가 1개이다 : 이 경우, 일단 양 끝 중 개수가 더 많은 격자는 무조건 보존한다. 하지만 다른 한 쪽은 그냥 버릴 순 없다. 아까 칸막이 2개를 써서 2칸을 보호했는데, 남은 다른 끝쪽이 5칸일 수도 있기 때문이다. 따라서 마지막으로 더해준 stop + 1번째 값과 다른 한 쪽 값을 비교한다.

 

3. 남은 칸막이가 0개이다 : 양끝을 모두 막는 데에 2개, 마지막으로 보존한 말과 말 사이 격자를 위해 2개로 결국 개수가 같다. 따라서 양 끝단의 격자 개수를 합한 것과, 마지막으로 더해준 말과 말 사이 격자 개수를 비교한다.

 

이를 통해 가장 많은 격자를 보존할 수 있다.

전체 코드는 다음과 같다.

public class Main {

	public static void main(String[] args) throws IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		int N = Integer.parseInt(st.nextToken());
		int K = Integer.parseInt(st.nextToken());
		int D = Integer.parseInt(st.nextToken());
		
		int[] horse = new int[K];
		
		st = new StringTokenizer(br.readLine());
		for (int i = 0; i < K; i++) {
			int n = Integer.parseInt(st.nextToken());
			horse[i] = n - 1;
		}
		
		List<Integer> list = new ArrayList<>();
		int[] one = new int[2];
		
		one[0] = horse[0];
		one[1] = N - 1 - horse[K-1];
		Arrays.sort(one);
		
		for (int i = 1; i < K; i++) {
			int diff = horse[i] - horse[i-1] - 1;
			if(diff != 0) list.add(diff); 
		}
		
		list.sort(null);
		
		int d = 0;
		int max = 0;
		int stop = list.size();
		int M = stop;
		
		for (int i = M - 1; i >= 0; i--) {
			int cur = list.get(i);
			if(d + 2 <= D) {
				d += 2;
				max += cur;
			} else {
				stop = i;
				break;
			}
		}
		
		if(D - d >= 2) {
			max += one[0] + one[1];
		} else if (D - d == 1) {
			max += one[1];
			if(stop + 1 < M) {
				if(list.get(stop + 1) < one[0]) {
					max -= list.get(stop + 1);
					max += one[0];
				}
			}
		} else if(D == d){
			if(stop + 1 < M) {
				if(list.get(stop + 1) < one[0] + one[1]) {
					max -= list.get(stop + 1);
					max += one[0] + one[1];
				}
			}
		}
		System.out.println(max);
	}

}