[JO] 2577 회전초밥 - JAVA

1. 문제

BOJ 2531번과 동일한 문제다.

JUNGOL

 

2531번: 회전 초밥

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

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

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. 풀이

처음에는 너무 어렵게 접근해서 Set 배열을 만들었다가 메모리초과가 났다.

그런데 다시 생각해보니 어차피 처음과 끝만 체크하는데 굳이 반복문을 쓰거나 set을 쓸 필요가 없다는 생각이 들었다.

입력

입력 부분이다. 여기에 count배열도 같이 만들어놓았다. 접시는 D번까지 있으므로 D+1만큼의 칸이 필요하다.

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[] input = new int[N];
int[] count = new int[D+1];

for(int i=0;i<N;i++) {
   input[i] = Integer.parseInt(in.readLine());
}

 

첫 번째 묶음

C는 쿠폰 초밥이라 count[C]는 항상 1 이상이다. max값도 쿠폰초밥 개수인 1로 초기화했다.

첫 번째 묶음은 K만큼 반복하면서 중복되지 않는 게 몇 개인지 세야 한다. 그래야 다음 묶음을 탐색할 때 이 값에서 계산할 수 있다.

i번째초밥번호로 count배열에 접근해서 +1한다. 

만약 +1한 값이 1이라면 처음 먹는 초밥 번호이므로 가짓수를 +1한다.

count[C] = 1;
int max = 1;
for(int i=0;i<K;i++){
   if(++count[input[i]]==1) max++;
}

 

나머지 탐색

첫번째 묶음 값 max를 tmp(계속 바뀔 묶음개수)에 넣는다.

0은 위에서 이미 탐색했으므로 start를 1부터 N-1까지 바꾸면서 탐색한다.

end값은 마지막 접시의 번호다. start+K-1한 값에 나머지연산을 하면 된다. 나머지 연산을 하는 이유는, start+K값이 N을 넘어갈 때가 있는데 문제에서 "회전"초밥이라고 했기 때문이다.

 

1. 그 전의 첫 번째 값은 이번 묶음에 포함되지 않으므로 -1을 한다. 이 결과가 0이 된다면 tmp도 -1해야한다.

2. 이번 묶음의 마지막 값을 +1한 뒤, 그 결과가 1이라면 처음 먹는 초밥이므로 tmp를 +1한다.

3. 마지막으로 tmp와 max값을 비교해 더 큰 값을 max에 저장한다. 

 

int tmp = max;
int start,end;
for(start = 1; start<N;start++){
   end = (start+K-1)%N;
   if(--count[input[start-1]]==0) --tmp;
   if(++count[input[end]]==1) ++tmp;

   max = Math.max(max,tmp);
}

System.out.println(max);

---

3. 결과