[BOJ] 23889. 돌 굴러가유

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

23889번: 돌 굴러가유

풀이

매우 어렵게 푼 문제. 접근 방식도 생각해내기 어려웠는데 그걸 구현하는 것도 쉽지 않았다. 파이썬으로 하면 금방 끝나던데 자바로 하니까 쉽지가 않구만,,

돌이 굴러가기 시작하는 시작 위치에 벽을 둬야 하는건 당연하고, 그 중에서도 어디에 둬야 하는가를 고르는게 중요했다. 문제의 예시를 예로 들면 돌이 [1, 4, 5]번에 떨어지고 1~3 / 4 / 5~7까지로 나누어서 파괴되는 모래성을 세보면 10 / 7 / 15이다. 여기서 벽은 2개만 세울 수 있으므로 1, 5에 벽을 세우면 피해를 최소화할 수 있다. 이걸 코드로 구현하면 된다.

코드

package greedy;

import java.util.*;
import java.io.*;

public class boj_23889_돌굴러가유 {

    static int N, M, K;
    static int[] town, stone;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());
        town = new int[N];
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            town[i] = Integer.parseInt(st.nextToken());
        }
        stone = new int[K];
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < K; i++) {
            stone[i] = Integer.parseInt(st.nextToken());
        }

        //각 돌의 위치부터 다음 돌의 위치까지 굴렀을 때 파괴될 모래성의 수를 센다.
        List<Destroy> destroy = new ArrayList<>();
        for (int i = 0; i < K - 1; i++) {
            int sum = 0;
            int start = stone[i] - 1;
            int end = stone[i + 1] - 1;

            for (int j = start; j < end; j++) {
                sum += town[j];
            }

            destroy.add(new Destroy(stone[i], sum));
        }
        int lastStone = stone[K - 1];
        int lastSum = 0;
        for (int i = lastStone - 1; i < N; i++) {
            lastSum += town[i];
        }
        destroy.add(new Destroy(lastStone, lastSum));

        //파괴된 모래성을 기준으로 내림차순 정렬.
        //만약 같다면 위치 사전순 오름차순 정렬.
        destroy.sort((x, y) -> {
            int result = Integer.compare(y.cnt, x.cnt);
            if (result == 0) {
                return Integer.compare(x.pos, y.pos);
            }
            return result;
        });

        //가장 많이 파괴되는 곳부터 벽을 세운다.
        destroy = destroy.subList(0, M);
        List<Integer> ans = new ArrayList<>();
        for (Destroy d : destroy) {
            ans.add(d.pos);
        }

        Collections.sort(ans);
        for (Integer i : ans) {
            System.out.println(i);
        }
    }

    static class Destroy {

        int pos, cnt;

        public Destroy(int pos, int cnt) {
            this.pos = pos;
            this.cnt = cnt;
        }
    }
}