[백준/c++] 2531번: 회전 초밥

 

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

2531번: 회전 초밥

 

- 같은 종류의 초밥이 둘 이상 있을 수 있다.

- 벨트의 임의의 한 위치부터 k개의 접시를 연속해서 먹을 경우 할인된 정액 가격으로 제공

- 고객에게 초밥 종류 하나가 쓰인 쿠폰을 발행하고 위의 상황이라면 이 쿠폰에 적힌 종류의 초밥 하나를 추가로 무료 제공. 번호에 적힌 초밥이 없다면 새로 만들어 제공

 

벨트 상태, 초밥의 가짓수, 연속해서 먹는 접시 개수(k), 쿠폰 번호가 주어졌을 때 먹을 수 있는 초밥 가짓수의 최댓값

가짓수의 최댓값을 구해야하므로 연속된 초밥을 중복된 수가 없도록 구성해보자.

k개의 접시를 먹으면 쿠폰 속 초밥을 무료로 먹을 수 있으니 중복된 수가 없는 초밥을 연속으로 k개를 먹는데, 쿠폰 초밥이 없도록 하면 되지 않을까?

 

예시) k=4, 30번 초밥 쿠폰

초밥 종류: 2, 7, 9, 25, 30

k개를 연속해서 먹어보면 (9-7-30-2), (30-2-7-9), (2-7-9-25) 이렇게 구성할 수 있다. 

여기서 (2-7-9-25)를 고르면 초밥 30을 무료로 먹을 수 있다. 

5가지 초밥을 먹을 수 있다.

 

 

---

 

 

이 문제는 이해를 잘못해서.. 틀린 문제였다 흑흑

처음에는 연속으로 초밥 종류 k개를 먹은 경우에만 쿠폰 초밥을 사용할 수 있는 것으로 생각했는데

계속 틀렸다고 해서 다시 문제를 읽고 진행해봤다.

다시 보니 연속으로 초밥 k개를 먹은 경우, 쿠폰 초밥을 사용할 수 있는 것이었다! 후^^

 

 

문제를 잘 읽자. 독해력의 중요성...

바로 풀 수 있을 만큼 쉬운 문제였는데 빙빙 돌아 오래 걸렸다ㅠ

 

#include <iostream>
#include <algorithm>
using namespace std;

int main(){
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int n, d, k, c;
    int sushi[30001];
    bool check[30001] = {false};
    bool coupon = false;
    int ans = -1;
    int cnt = 0;
    cin >> n >> d >> k >> c;
    for(int i=0; i<n; i++) cin >> sushi[i];
    
    for(int i=0; i<n; i++){
        for(int j=0; j<k; j++){         //k개 먹음
            int cur = sushi[(i+j)%n];
            if(cur == c) coupon = true; //쿠폰 초밥을 먹음
            if(!check[cur]){            //먹은 적 없는 초밥 종류
                cnt++;                  //초밥 종류 카운팅
                check[cur] = true;      //먹은 적 있는 초밥으로 변경
            }
        }
        if(!coupon) ans = max(ans, cnt+1); //쿠폰 초밥을 먹지 않은 경우
        else        ans = max(ans, cnt);   //쿠폰 초밥을 먹은 경우
        
        //초기화
        coupon = false;
        cnt = 0;
        for(int i=1; i<=d; i++) check[i] = false;
    }
    cout << ans << '\n';
    return 0;
}

 

 

고군분투의 흔적...