[백준] 2531번 회전 초밥

문제: 2531번: 회전 초밥

basic-algo-lecture/workbook/0x14.md at master · encrypted-def/basic-algo-lecture

basic-algo-lecture/workbook/0x14.md at master · encrypted-def/basic-algo-lecture

 

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <limits>

using namespace std;

int main(void) {
    ios::sync_with_stdio(0);
    cin.tie(0);

    int n, d, k, c;
    cin >> n >> d >> k >> c;
    vector<int> chobabs(n);
    for (int i = 0; i < n; i++) {
        cin >> chobabs[i];
    }
    vector<int> used(d + 1); // 0번 인덱스 안 써!
    
    int st = 0;
    int en = 0;
    int selectedCnt = 0;
    int uniqueCnt = 0;
    int ans = 0;
    while (st < n) {
        // 회전 초밥이니까 en 이 끝에 도달하면 값을 0으로 다시 바꿔줭..
        if (en == n) {
            en = 0;
        }

        // 현재 연속한 초밥 접시가 k 보다 적ㅇ르 때에는 걍 en 증가시켜
        if (selectedCnt < k) {
            selectedCnt++;
            if (used[chobabs[en]] == 0) {             
                uniqueCnt++;
            }
            used[chobabs[en]]++;
            en++;  
        }
        else if (selectedCnt == k) {
            // 쿠폰 초밥 추가 여부 확인
            int totalCnt = uniqueCnt;
            if (used[c] == 0) totalCnt++;
            if (totalCnt > ans) {
                ans = totalCnt;
            }

            // 앞쪽 초밥 제거
            if (used[chobabs[st]] == 1) {
                uniqueCnt--;
            }
            used[chobabs[st]]--;
            selectedCnt--;
            st++; // 이제 맨 앞에 있는 초밥 하나 삭제~
        }
    }
    cout << ans;

    return 0;
}

 

아... 너무 짜증난다. 문제를 잘못이해해서 시간을 많이 썼다 ㅠㅠㅠㅠㅠ;;;;

1. 원래 회전 초밥은 손님이 마음대로 초밥을 고르고, 먹은 초밥만큼 식대를 계산하지만, 벨트의 임의의 한 위치부터 k개의 접시를 연속해서 먹을 경우 할인된 정액 가격으로 제공한다.

2. 각 고객에게 초밥의 종류 하나가 쓰인 쿠폰을 발행하고, 1번 행사에 참가할 경우 이 쿠폰에 적혀진 종류의 초밥 하나를 추가로 무료로 제공한다. 만약 이 번호에 적혀진 초밥이 현재 벨트 위에 없을 경우, 요리사가 새로 만들어 손님에게 제공한다.

 

아니 나는 위 문제 조건을 보고 쿠폰으로 사용하는 초밥도 연속해서 붙어 있어야 하는 건줄 알았다.. 그래서 괜히 조건문 더 붙이고 난리 치느라 계속 꼬였던 거였다...

 

문제를 다시보니까 1번 행사에 참여했으면 쿠폰으로 쓰는 초밥은 그냥 얻는거더라.. 만약 쿠폰 초밥이 처음 만난 종류의 초밥이면 단순하게 그냥 uniqueCnt 값에 +1 해주면 되는거였다..

 

아.. 짜증나