회전 초밥 (백준 15961번)

 

문제

문제 링크 : www.acmicpc.net/problem/2531

2531번: 회전 초밥

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
1초	512 MB	2109	813	565	37.392%

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

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

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가지 종류의 초밥을 먹을 수 있다.

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

입력

첫 번째 줄에는 회전 초밥 벨트에 놓인 접시의 수 N, 초밥의 가짓수 d, 연속해서 먹는 접시의 수 k, 쿠폰 번호 c가 각각 하나의 빈 칸을 사이에 두고 주어진다. 단, 2 ≤ N ≤ 3,000,000, 2 ≤ d ≤ 3,000, 2 ≤ k ≤ 3,000 (k ≤ N), 1 ≤ c ≤ d이다. 두 번째 줄부터 N개의 줄에는 벨트의 한 위치부터 시작하여 회전 방향을 따라갈 때 초밥의 종류를 나타내는 1 이상 d 이하의 정수가 각 줄마다 하나씩 주어진다.

출력

주어진 회전 초밥 벨트에서 먹을 수 있는 초밥의 가짓수의 최댓값을 하나의 정수로 출력한다.

 

풀이

준비물 : 접시 N개, 초밥 종류(0~d)배열, k+1이 담긴 변수(서로다른 초밥 종류), 보너스개수

1. k번째 접시까지 받아가면서 초밥 종류를 기록해놓음. (만약 초밥 겹치는게 있으면 k+1에서 한개씩빼기)
2. 보너스도 마찬가지로 생각해주고, 보너스가 만약에 포함되어있으면 역시 k+1에서 한개 빼기
3. 이제 k번째부터~N+k번째까지 돌면서 뒤에 하나 추가, 앞에 하나 빼주기
4. 둘이 같으면 걍 진행하고
5. 둘이 달랐을때 초밥 종류랑 보너스 잘 바꿔가면서 정답을 찾아가기

 

코드

public class Main {
    public static StringBuilder sb = new StringBuilder();
    public static java.io.BufferedReader br = new java.io.BufferedReader(new java.io.InputStreamReader(System.in));
    static int N; //접시 수
    static int d; //초밥의 최대값
    static int k; //연속해서 최대
    static int c; //이벤트 초밥
    static int dishes[];
    static int sushi[];
    static int ans;
    
    public static void main(String[] args)throws Exception {
    	 String lines = br.readLine();
         String[] spl  = lines.split(" ");
         N=Integer.parseInt(spl[0]);
         d=Integer.parseInt(spl[1]);
         k=Integer.parseInt(spl[2]);	
         c=Integer.parseInt(spl[3]); 
         
         dishes = new int[N];
         sushi = new int[d+1];
         int temp = k+1;
         int bonus = 0;
         int past, now;
         
         //배열 초기화
         for(int i=1; i<d+1; i++) {
        	 sushi[i] = 0;
         }  
         //시작부터 k개 먼저
         for(int i=0; i<k; i++) {
        	 dishes[i] = Integer.parseInt(br.readLine());
        	 sushi[dishes[i]]++;
        	 if(sushi[dishes[i]] > 1) temp--;
        	 if(dishes[i] == c) bonus++;
         }
         if(bonus > 0) temp--;
         ans = temp;
         
         
         for(int i=k; i<N+k; i++) {
        	 if(i<N) {
            	 dishes[i] = Integer.parseInt(br.readLine());
            	 past = dishes[i-k];
            	 now = dishes[i];
        	 }
        	 else {
        		 past = dishes[i-k];
        		 now = dishes[i % N];
        	 }
        	 //만약 새로 추가한 값이 빼는 값이랑 같으면 할필요 x
        	 if(past == now){
        		 continue;
        	 }
        	 //둘이 다름
        	 else {
        		sushi[past]--;
        		//past가 0되었다는 소리는 past는 안겹치는 애였고, 걔가 하나 빠짐
        		if(sushi[past] == 0) temp--;
        		
        		sushi[now]++;
        		//now가 1이 되었다는 소리는, now는 새로 들어온 애
        		if(sushi[now] == 1) temp++;
        		
        		//이미 보너스가 0보다 크면(애초에 보너스가 안에 있었을때)
        		if(bonus > 0) {
        			if(now == c) bonus++;
        			if(past == c) { 
        				bonus--; 
        				if(bonus == 0) temp++;
        			}
        		}
        		//bonus == 0(보너스가 안에 없엇을때)
        		else {
        			if(now == c) {
        				bonus++;
        				temp--;
        			}
        		}
        	 }  	 
        	 ans = Math.max(temp, ans);
         }
         System.out.println(ans);
    }
}

 

결과