[랜덤 마라톤] Year of the Cow(21233)

1. 문제 풀이 아이디어

• 12년마다 오는 소의 해를 기준으로 방문해야 할 연도를 저장하고, 방문 연도 사이의 차이를 계산해 최소 이동 시간을 구한다.

• 방문해야 하는 연도의 차이를 정렬하여 큰 차이부터 제외하면 문제를 해결할 수 있다.

2. 나의 정답 코드

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer stringTokenizer = new StringTokenizer(bufferedReader.readLine());
        int n = Integer.parseInt(stringTokenizer.nextToken());
        int k = Integer.parseInt(stringTokenizer.nextToken());
        Set<Integer> set = new TreeSet<>();
        int max = 0;
        set.add(0);
        for (int i = 0; i < n; i++) {
            int c = Integer.parseInt(bufferedReader.readLine()) / 12 + 1;
            set.add(c);
            max = Math.max(max, c);
        }
        int result = max * 12;
        int prev = 0;
        List<Integer> list = new ArrayList<>();
        for (int i : set) {
            list.add(i - prev);
            prev = i;
        }
        list.sort(Comparator.reverseOrder());
        for (int i = 0; i < k - 1 && i < list.size(); i++) {
            result -= (list.get(i) - 1) * 12;
        }
        System.out.println(result);
        bufferedReader.close();
    }
}

3. 정리

• 소의 해를 기준으로 방문해야 할 연도를 set에 저장한다.

• 소의 해 중 현재로 돌아오는 것을 고려하여 0을 추가한다.

• 입력 값을 12로 나눈 값에 1을 더해 소의 해로 변환하고, 이를 set에 추가하며 최대값을 계산한다.

• 총 이동 시간을 max * 12로 초기화한다.

• 소의 해들 간의 차이를 list에 저장하고, 이를 내림차순으로 정렬하여 큰 차이를 제거한다.

• 가장 큰 k-1개의 차이를 제외한 이동 시간을 계산하여 결과값을 출력한다.