2012 한국정보올림피아드 시.도지역본선 고등부 2번 회전초밥(BOJ: 2531) 풀이
2018. 7. 25. 16:36
분류 : 큐, 시뮬레이션
초밥의 회전을 나머지연산을 이용하여 인덱싱을 간편하게 할 수 있습니다.
초기세팅
1. 0부터 k개의 초밥번호를 Q에 넣는다 (7,9,7,30)
2. 하나씩 넣으면서 (초밥종류배열[초밥[i]]==0) 이라면 cnt++ 한다.
3. 초밥종류배열[초밥[i]]++ 한다.
4. Max = cnt;
5. (초밥종류배열[쿠폰초밥] == 0) 이라면 max +1 한다
6. end = k-1
N번 반복
1. Dequeue한다(U). 초밥종류배열[U]-- 한다.
2. 초밥종류배열[U]==0 이라면 cnt--한다.
3. end = (end+1)%N //이부분이 중요 회전초밥 이므로 끝이라면 다시 앞으로 가야함.
4. 초밥종류배열[초밥[end]]==0 이라면 cnt++한다.
5. 초밥종류배열[초밥[end]]++;
6. if(초밥종류배열[쿠폰초밥]==0) -> cnt+1 > max -> max = cnt+1;
else cnt > max -> max = cnt;
#include <stdio.h> int flg[3001]; int data[30001]; int N,d,k,c; int main() { //freopen("Text.txt", "r", stdin); scanf("%d %d %d %d", &N, &d, &k, &c); for (int i = 0; i < N; i++) { scanf("%d", &data[i]); } int sum=0; int max; for (int i = 0; i < k; i++) { if (flg[data[i]] == 0) { sum++; } flg[data[i]]++; } max = sum; if (flg[c] == 0) { max++; } int start = 0; int end = k - 1; for (int i = 0; i < N - 1; i++) { flg[data[start]]--; if (flg[data[start]] == 0) { sum--; } start++; end = (end + 1) % N; if (flg[data[end]] == 0) { sum++; } flg[data[end]]++; if (flg[c] == 0) { if (sum + 1 > max) { max = sum + 1; } } else { if (sum > max) { max = sum; } } } printf("%d\n", max); return 0; }
'IT > 정보올림피아드,문제해결' 카테고리의 다른 글
2006 한국정보올림피아드 KOI 고등부 1번 기지국(BOJ: 2300) 풀이 (0) | 2018.07.25 |
---|---|
퀵소트구현 (0) | 2018.07.13 |
2013 한국정보올림피아드 시.도지역본선 고등부 4번 앱(BOJ: 7579) 풀이 (0) | 2018.07.06 |