[Baekjoon] 15961번: 회전 초밥

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

15961번: 회전 초밥

문제 설명

문제가 길기 때문에 천천히 꼼꼼히 읽어보면서 문제와 조건을 이해해야 한다. 예제 입력 1을 통해 알아보자.

초밥이 위처럼 주어진다고 한다. 이 중에 어떤 한 접시부터 연속으로 k개의 접시를 먹으면 할인을 해주는 이벤트를 한다고 한다. 그리고 이 이벤트에 참여하면 서비스 초밥을 하나 더 준다고 한다. 이 초밥이 트레이에 없으면 하나 만들어서 준다고 한다. 이 이벤트를 모두 활용해 가장 많은 종류의 초밥을 먹을 수 있는 경우의 종류 개수를 출력해야 한다.

위 예제에선 서비스 초밥 번호가 30이므로 2, 7, 9, 25를 먹으면 4종류 + 서비스 초밥 1종류로 최대 5종류의 초밥을 먹을 수 있다.

풀이 방법

이 문제는 슬라이딩 윈도우를 활용해서 해결할 수 있다. 다시 예제 입력 1을 활용해 살펴보자.

제일 왼쪽 7번을 1번으로 시작한다. k가 4이므로 연속으로 4개를 먹어야 이벤트에 참여할 수 있다. 그렇다면 처음 먹을 수 있는 초밥들은 다음과 같다.

첫 번째

위처럼 먹은 경우 7이 중복되므로 먹은 초밥의 종류는 3가지(7, 9, 30)이 된다. 그 다음 먹을 수 있는 초밥들은 다음과 같다.

두 번째

이 경우 먹은 초밥의 종류는 4가지(2, 7, 9, 30)가 된다.

세 번째

이 경우 먹은 초밥의 종류는 4가지(2, 7, 30)가 된다.

어떻게 이동되는지 감이 올 것이다. 첫 번쨰 초밥을 빼고 다음 초밥을 더해가면서 k의 크기를 유지하는 것이다.

네 번째

이 경우 먹은 초밥의 종류는 4가지(2, 7, 9, 30)가 된다.

다섯 번째

이 경우 먹은 초밥의 종류는 4가지(2, 7, 9, 25)가 된다.

여섯 번째

이 경우 먹은 초밥의 종류는 3가지(7, 9, 25)가 된다.

일곱 번째

이 경우 먹은 초밥의 종류는 3가지(7, 9, 25)가 된다.

여덟 번째

이 경우 먹은 초밥의 종류는 3가지(7, 9, 25)가 된다.

이렇게 탐색을 한 결과 최대로 먹을 수 있는 초밥 종류의 개수는 4개이다. 여기에 연속으로 먹었을 경우 주는 서비스 초밥은 항상 주어지기 때문에 1을 더해주면 결과적으로 먹을 수 있는 초밥 종류의 최대 개수는 5개가 된다.

 

전체 코드를 보며 구현 부분을 살펴보자. 주석에 상세 설명을 적어놓았다.

import java.io.*;

class Main {

    static int[] sushis;
    static int[] eaten;

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

        String[] split = br.readLine().split(" ");
        int N = Integer.parseInt(split[0]);
        int d = Integer.parseInt(split[1]);
        int k = Integer.parseInt(split[2]);
        int c = Integer.parseInt(split[3]);
        int max = 0;

        // 초밥 개수 + 연속된 스시 범위를 맨 뒤에 붙이기 위한 k - 1
        // 여섯 번째 ~ 여덟 번째에 대한 처리를 쉽게 하기 위한 처리이다.
        sushis = new int[N + k - 1];
        // 먹은 초밥을 확안하기 위한 배열
        eaten = new int[d + 1];
        eaten[c] = 1; // 쿠폰 초밥 먹은 처리
        max = 1; // 쿠폰 초밥 먹은 처리

        // N개만큼 입력받기
        for (int i = 0; i < N; i++) {
            sushis[i] = Integer.parseInt(br.readLine());
        }

        // 맨 뒤에 앞쪽 스시 붙이기
        for (int i = 0; i < k - 1; i++) {
            sushis[N + i] = sushis[i];
        }

        int left = 0;
        int right = k;
        for (int i = left; i < right; i++) {
            // 먹었던 스시가 아니라면 최댓값 증가
            if (eaten[sushis[i]] == 0) {
                max++;
            }
            // 먹은 스시 개수 증가
            eaten[sushis[i]] += 1;
        }

        int result = max;
        for (; right < sushis.length; right++) {
            // 처음 먹은 스시 개수 차감
            eaten[sushis[left]] -= 1;
            // 처음 먹은 스시를 또 안 먹었으면 먹은 초밥 총 개수 감소
            if (eaten[sushis[left]] == 0)
                result -= 1;
            // 다음 먹을 스시가 처음 먹는 거라면 먹은 초밥 총 개수 증가
            if (eaten[sushis[right]] == 0)
                result += 1;
            // 다음 먹을 스시 개수 증가
            eaten[sushis[right]] += 1;
            max = Math.max(max, result);
            left++;
        }

        System.out.println(max);
    }
}