[BOJ] 15961 회전초밥 - JAVA

1. 문제

15961번: 회전 초밥

회전 초밥 음식점에는 회전하는 벨트 위에 여러 가지 종류의 초밥이 접시에 담겨 놓여 있고, 손님은 이 중에서 자기가 좋아하는 초밥을 골라서 먹는다. 초밥의 종류를 번호로 표현할 때, 다음 그림은 회전 초밥 음식점의 벨트 상태의 예를 보여주고 있다. 벨트 위에는 같은 종류의 초밥이 둘 이상 있을 수 있다.

새로 문을 연 회전 초밥 음식점이 불경기로 영업이 어려워서, 다음과 같이 두 가지 행사를 통해서 매상을 올리고자 한다.

1. 원래 회전 초밥은 손님이 마음대로 초밥을  고르고, 먹은 초밥만큼 식대를 계산하지만, 벨트의 임의의 한 위치부터 k개의 접시를 연속해서 먹을 경우 할인된 정액 가격으로 제공한다. 
2. 각 고객에게 초밥의 종류 하나가 쓰인 쿠폰을 발행하고, 1번 행사에 참가할 경우 이 쿠폰에 적혀진 종류의 초밥 하나를 추가로 무료로 제공한다. 만약 이 번호에 적혀진 초밥이 현재 벨트 위에 없을 경우, 요리사가 새로 만들어 손님에게 제공한다.  

위 할인 행사에 참여하여 가능한 한 다양한 종류의 초밥을 먹으려고 한다. 위 그림의 예를 가지고 생각해보자. k=4이고, 30번 초밥을 쿠폰으로 받았다고 가정하자. 쿠폰을 고려하지 않으면 4가지 다른 초밥을 먹을 수 있는 경우는 (9, 7, 30, 2), (30, 2, 7, 9), (2, 7, 9, 25) 세 가지 경우가 있는데, 30번 초밥을 추가로 쿠폰으로 먹을 수 있으므로 (2, 7, 9, 25)를 고르면 5가지 종류의 초밥을 먹을 수 있다. 

회전 초밥 음식점의 벨트 상태, 메뉴에 있는 초밥의 가짓수, 연속해서 먹는 접시의 개수, 쿠폰 번호가 주어졌을 때, 손님이 먹을 수 있는 초밥 가짓수의 최댓값을 구하는 프로그램을 작성하시오. 

---

2. 풀이

1.  연속해서 먹은 접시에 어떤 종류, 몇 접시가 있는지 eat 배열에 저장한다.

2.  쿠폰 초밥위치에 1을 미리 저장해둔다.

3.  첫번째 초밥부터 K개 연속해서 먹은 상황으로 초기화한다. 미리 쿠폰초밥을 받았으므로 tmp=1부터 시작이다. 만약 eat[초밥번호]가 0이었을때만 tmp++한다.

4.  초기화한 후 max값을 tmp로 두고 시작한다.

5.  start 값이 1부터 N이 되기 전까지 탐색한다. end값은 start+K이므로 %연산을 사용한다. start-1에 있는 초밥은 갯수를 하나 빼고, end에 있는 초밥은 갯수를 더한다. 

6.  start를 옮길 때마다 max와 tmp 중 더 큰 값으로 max를 갱신한다.

7.  max를 출력한다.

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

public class BOJ_15961_회전초밥 {
   public static void main(String[] args) throws IOException {
      BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
      StringTokenizer st = new StringTokenizer(in.readLine());
      int N = Integer.parseInt(st.nextToken());  //접시 수
      int D = Integer.parseInt(st.nextToken());  //초밥 가짓수
      int K = Integer.parseInt(st.nextToken());  //연속해서 먹는 접시 수
      int C = Integer.parseInt(st.nextToken());  //쿠폰번호

      //벨트에 놓여있는 초밥들
      int[] sushi = new int[N];
      for(int i=0;i<N;i++) sushi[i] = Integer.parseInt(in.readLine());

      //이미 먹은 초밥 종류
      int[] eat = new int[D+1];
      eat[C] = 1;

      //초기화
      int tmp = 1, start, end = K;
      for(start=0;start<end;start++){
         if(eat[sushi[start]]++ == 0) tmp++;
      }
      int max = tmp;

      //탐색
      for(start = 1;start<N;start++, end=(end+1)%N){
         if(--eat[sushi[start-1]]==0) tmp--;
         if(eat[sushi[end]]++ == 0) tmp++;
         if(max<tmp) max = tmp;
      }

      //출력
      System.out.println(max);

   }
}

---

3. 결과