[BaekJoon][2531] 회전 초밥

BAEKJOON ONLINE JUDGE

2531 회전 초밥

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

연속해서 먹을 수 있는 접시가 k 개 이기 때문에 회전(순환)의 경우 배열을 추가로 k개 더 선언하여 뒤에 더 입력하였다.

dp로 문제를 풀었다.

dp[마지막으로 먹은 초밥의 index] = index의 초밥을 마지막으로 먹었을 경우 최대로 먹은 초밥의 가짓 수

k개 안에 중복되는 초밥번호가 있을 경우 더이상 수를 세면 안되기 때문에 이를 처리해야 한다.

초밥의 접시 여부를 판단하는 배열을 선언하여 i 번째 초밥을 추가하면 i - k의 초밥을 빼 준다.

또한 연속으로 초밥을 먹으면서 쿠폰 번호와 동일한 초밥을 먹을 수 있으므로 이를 판단하여야 한다.

dp를 채워나갈 때 같이 계산을 하면 된다.

하지만, 문제를 풀다보니 일단은 따로 계산을 하였다. (문제를 잘못 읽어서 많이 틀렸다!ㅠㅠ)

최종적으로, dp - 쿠폰의 여부 + 쿠폰 이벤트(1) 을 한 결과 중 최대값을 출력하면 된다.

#include <stdio.h>
 
int n, d, k, c;
int input[33001];
int ch[3001];
int count[33001];
int coupon[33001];
 
void countmax()
{
    int i;
    int cnt;
 
    for (i = 1; i <= k; i++) {
        cnt = count[i - 1];
        if (cnt < k && !ch[input[i]])    cnt++;
        count[i] = cnt;
        ch[input[i]]++;
    }
 
    for (; i <= n + k; i++) {
 
        ch[input[i - k]]--;
 
        if (ch[input[i - k]] == 0)    cnt--;
 
        if (cnt < k && !ch[input[i]]) cnt++;
 
        count[i] = cnt;
        ch[input[i]]++;
 
        coupon[i] = ch[c];
    }
}
 
int main()
{
    int i;
    int max = 0;
 
    scanf("%d %d %d %d", &n, &d, &k, &c);
 
    for (i = 1; i <= n; i++) {
        scanf("%d", &input[i]);
    }
    for (; i <= n + k; i++) {
        input[i] = input[i - n];
    }
 
    countmax();
 
    for (i = k + 1; i <= n + k; i++) {
        if (coupon[i])        count[i]--;
        if (count[i] > max)
            max = count[i];
    }
 
    printf("%d\n", max + 1);
 
    return 0;
}