[ BOJ ] 15961. 회전 초밥 G4 JAVA

 

---

---

문제 이해

새로 문을 연 회전 초밥 음식점이 불경기로 영업이 어려워서, 다음과 같이 두 가지 행사를 통해서 매상을 올리고자 한다. 원래 회전 초밥은 손님이 마음대로 초밥을  고르고, 먹은 초밥만큼 식대를 계산하지만, 벨트의 임의의 한 위치부터 k개의 접시를 연속해서 먹을 경우 할인된 정액 가격으로 제공한다.  각 고객에게 초밥의 종류 하나가 쓰인 쿠폰을 발행하고, 1번 행사에 참가할 경우 이 쿠폰에 적혀진 종류의 초밥 하나를 추가로 무료로 제공한다. 만약 이 번호에 적혀진 초밥이 현재 벨트 위에 없을 경우, 요리사가 새로 만들어 손님에게 제공한다. 위 할인 행사에 참여하여 가능한 한 다양한 종류의 초밥을 먹으려고 한다. 위 그림의 예를 가지고 생각해보자. k=4이고, 30번 초밥을 쿠폰으로 받았다고 가정하자. 쿠폰을 고려하지 않으면 4가지 다른 초밥을 먹을 수 있는 경우는 (9, 7, 30, 2), (30, 2, 7, 9), (2, 7, 9, 25) 세 가지 경우가 있는데, 30번 초밥을 추가로 쿠폰으로 먹을 수 있으므로 (2, 7, 9, 25)를 고르면 5가지 종류의 초밥을 먹을 수 있다. 회전 초밥 음식점의 벨트 상태, 메뉴에 있는 초밥의 가짓수, 연속해서 먹는 접시의 개수, 쿠폰 번호가 주어졌을 때, 손님이 먹을 수 있는 초밥 가짓수의 최댓값을 구하는 프로그램을 작성하시오.

아이디어

1. 서로 다른 수의 초밥을 K개 뽑는다. 2. 뽑힌 초밥들과 쿠폰에 쓰인 초밥 종류가 다른 집합을 찾는다.(같으면 더하지말고) 3. 출력한다. 관건은 k개의 연속된 초밥을 어떻게 뽑을지였다. 그냥 쿠폰초밥을 미리 check배열에 넣어두고 cnt를1부터시작한다. 일단미리4개넣어놓고, 맨앞을 빼고 (기존4개까지+1)의위치를 붙여주면 다시 새로운 그룹이 된다. 카운트는 0일때 넣을때 +1, 뺐는데 0이 되면 -1 해주고, 맥스값을 갱신해간다.

코드

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

public class Main {
	
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.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(br.readLine());
		System.out.println(max(sushi,D,K,C));
	}
	static int max(int[] sushi, int D, int K, int C) {
		int[] check = new int[D+1];			// 이미 뽑혔는지 체크
		int cnt =1;							// cnt변수C를넣어놔서1부터시작
		check[C]++;							// 미리 넣어둔다.
		for(int i=0;i<K; ++i) if(check[sushi[i]]++ == 0) cnt++;	// 처음4자리를넣는다
		int max = cnt;						// 반환할 변수
		for(int i=0;i<sushi.length;++i) {
			if(check[sushi[(i+K)%sushi.length]]++ == 0) cnt++;	// 안뽑혔던상태면 카운팅
			if(--check[sushi[i]]==0)cnt--;	// 뺐는데 0이면 카운트빼준다.
			max=Math.max(max, cnt);			// 최대값갱신
		}
		return max;
	}
}

 

 

 

---

집사는개발자가되고파