[백준] 2531. 회전 초밥 - python

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

난이도: 실버 1

알고리즘: 구현?

풀이과정

가장 많은 종류의 초밥을 먹을 수 있는 경우를 구하는 문제다. k개의 연속된 수열에서 서로 다른 숫자가 나오고, 쿠폰으로 받는 종류까지 고려해야 한다.

 

for i in range(0, n + k - 1)

0 ~ n + k - 1번까지 반복한다. n이 아닌 n + k - 1인 이유는 초밥의 마지막 줄에서 시작해서 초밥의 처음이 다음에 오는 경우까지 고려해야 하기 때문이다.

cur = set()
for x in range(k):
    cur.add(board[(i + x) % n])
cur.add(c)

현재 연속된 k개의 수열에서 곂치는 숫자가 없음을 보장하기 위해서 set 자료형을 사용한다. 또한 n + k - 1 부분을 위해 %n 연산을 통해 인덱스가 벗어나지 않도록 처리해 준다.

 

마지막으로 연속되는 k개의 수열에서 쿠폰으로 받을 수 있는 초밥인 c도 추가해주면, set 자료형의 길이가 현재 상황에서 먹을 수 있는 초밥 종류의 개수가 된다.

answer = max(answer, len(cur))

 위와 같이 answer를 갱신하며 답을 구하면 된다.

 

소스코드

import sys
input = sys.stdin.readline

n, d, k, c = map(int, input().split())
board = []
for _ in range(n):
    board.append(int(input()))
answer = 1
for i in range(0, n + k - 1):
    cur = set()
    for x in range(k):
        cur.add(board[(i + x) % n])
    cur.add(c)
    answer = max(answer, len(cur))
print(answer)