백준 2531번 회전 초밥 (C++)

알고리즘 개념: 투포인터

투포인터에 대해 잘 모른다면 이전에 정리해 둔 개념 정리를 한번 읽어보고 오는 것을 추천합니다. 

알고리즘 공부 2주차: 투포인터 개념

알공 2주차: 투포인터 개념

백준 2531번 회전 초밥

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

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

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

입력

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

출력

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

예제 보려면 더보기 클릭

예제 입력 1

8 30 4 30
7
9
7
30
2
7
9
25

예제 출력 1

5

예제 입력 2

8 50 4 7
2
7
9
25
7
9
7
30

예제 출력 2

4

---

문제 설명

개인적으로 가장 어려운 문제 중 하나였다.. (시도만 nn번) 

밑에 제출코드를 보면 알겠지만 너무 어려워서 주석처리 되어 있는 부분이 많은데 하나하나 짚어보도록 하겠다.

문제에도 나와있지만 매끄럽게 설명하기 위해 다시 문제 해석부터 해보자.

8 30 4 30
7
9
7
30
2
7
9
25

8개의 초밥이 나열되어있고, 초밥의 가짓수는 30개이며 4개씩 연속으로 먹을 경우 30번 초밥을 먹을 수 있다. 

초밥을 연속해서 4개씩 먹었을때 나올 경우는 (7,9,7,30) ~ (2,7,9,25)까지 다양한 경우가 나올 수 있는데 만약 (2,7,9,25) 순서대로 초밥을 먹을 경우 서비스로 받는 30번 초밥까지 총 5가지의 초밥을 먹는 것이다. 

우리는 최대한 다양한 초밥을 많이 먹기 위한 경우를 찾아야 하는데 여기서 중요한 점이 있다. 

초밥을 연속해서 4개 먹었을때 최댓값은 4이고 만약 이 초밥 중에 쿠폰 번호가 없다면 최댓값은 5인 것이다!

이걸 문제에 적용해 보면 쿠폰 번호 c가 포함되지 않는다면 연속해서 먹는 접시의 수 k가 최댓값이고, 포함된다면 k+1이다. 

그럼 이걸 코드로 작성한다면, 나는 초밥의 종류별로 정리할 새로운 배열 arr을 만들었다. 

원래 배열이 7이라는 숫자가 들어가면 arr [7]++을 해주며 개수를 세는 것이다. (이때 arr은 0으로 초기화되어있어야한다.)

그리고 투포인터를 사용해 모든 경우의 수에 접근하며 초밥이 포함될 때마다 각 개수를 count 해주고, 그때마다 해당 초밥의 arr개수를 늘려주는 것이다. 

여기서 arr에 처음과 끝 부분에 접근하는 방법에서 막히는 경우가 많다.

특히 회전초밥처럼 빙글빙글 도는 모양이기에 끝부분에 대한 접근이 어렵다고 느껴질 수 있지만 사실 간단하다. 

초밥의 종류 n을 나눈 나머지를 계산하면 되는 것이다. 잘 이해가 안 되면 숫자를 대입해 보자. 

초밥의 종류가 7가지인데 내가 접근하고자 하는 수는 8이다. 그럼 1에 접근하기 위해서는? 8%7을 통해 계산하는 것이다. 

그리고 나는 여기서 끝 초밥에 접근하기 위해 해당 인덱스에 +k를 해주었는데, 이걸 코드로 작성해 보면 다음과 같다. 

for (int i = 1; i < n; i++) {
		//end 이동
		if (arr[v[(i + k - 1) % n]] == 0)count++;
		arr[v[(i + k - 1) % n]]++;
		//배열 길이 n이상 넘어가면 %n해주기 
		
		//start 이동
		arr[v[i - 1]]--;//한번 먹을때마다 줄기
		if (arr[v[i - 1]] == 0) count--;
	}

처음 부분은 i-1로 끝부분은 (i+k-1)% n으로 접근하며 모든 경우의 수를 살펴보는 것이다. 

여기서 슬라이딩 윈도우를 살펴볼 수 있다. 

슬라이딩 윈도우 : 특정 구간의 길이(범위)내에서 이동하며 조건에 맞는 경우의 수를 찾는 것

이런 면에서 내 코드는 투포인터보단 슬라이딩 윈도우에 가깝다고 볼 수 있다.

투포인터의 경우 유동적으로 반드시 포인터가 2개 필요하지만 슬라이딩 윈도우는 범위가 정해져 있기 때문에 코드에서 +k를 한 것과 같이 특정 다른 포인터를 만들어줄 필요 없기 때문이다.

여기까지 따라왔다면 이제 마무리만 지어주면 된다. 

앞서 말했던 쿠폰 번호의 경우의 수만 비교하면 되는 것인데, 이걸 위해 우리가 arr의 각 값을 +해주었으니까 arr[c]의 값이 0인지만 확인하면 되는 것이다. 

만약 초밥이 포함되어 있다면 쿠폰번호인 c의 초밥 개수 arr[c]는 +1 (또는 그 이상의 수)일 것이므로 max=count가 된다. 

(count는 현재 먹은 초밥의 개수이다.)

포함되어 있지 않다면 max=count+1을 해주면 되니 정말 간단하다.

마지막으로 max는 최댓값이여야 하니 아무때나 변경되지 않도록 if문을 설정해주면 코드 완성이다. 

 

---

제출한 코드(C++)

#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
using namespace std;
using ll = long long int;
int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int n, d, k, c;
	cin >> n >> d >> k >> c;
	//접시의 수 N, 초밥의 가짓수 d, 연속해서 먹는 접시의 수 k, 쿠폰 번호 c
	int v[30005] = { 0, };
	int arr[3005] = { 0, };
	//arr은 초밥의 종류별 개수
	for (int i = 0; i < n; i++) {
		cin >> v[i];
	}
	int count = 0, max = 0;
	//0번부터 k개수만큼 먹었다
	for (int i = 0; i < k; i++) {
		if (arr[v[i]] == 0) count++;
		//해당초밥을 먹은 개수
		arr[v[i]]++;
		//한번도 안먹었다면 count ++
	}
	//현재 최대 초밥의 종류 개수 
	max = count;
    	if (max <= count) {
			if (arr[c] == 0)//쿠폰번호가 포함되지 않다면
				max = count + 1;
			else
				max = count;
		}
	//슬라이딩 윈도우, 1~n-1번까지 이동
	for (int i = 1; i < n; i++) {
		//end 이동
		if (arr[v[(i + k - 1) % n]] == 0)count++;
		arr[v[(i + k - 1) % n]]++;
		//배열 길이 n이상 넘어가면 %n해주기 
		
		//start 이동
		arr[v[i - 1]]--;//한번 먹을때마다 줄기
		if (arr[v[i - 1]] == 0) count--;
		if (max <= count) {
			if (arr[c] == 0)//쿠폰번호가 포함되지 않다면
				max = count + 1;
			else
				max = count;
		}
	}
	cout << max;
}