[BOJ] 22862 - 가장 긴 짝수 연속한 부분 수열 (large) (Python)

 

 

아이디어

 

누적합으로 S에서 홀수 원소들을 최대 K번 삭제한 연속된 짝수 수열의 길이를 구한다.

 

 

풀이

 

22857번 가장 긴 짝수 연속한 부분 수열 (small)의 풀이 #2와 같다.

 

리스트 arr에는 홀수 원소로 구분된 짝수로 이루어진 수열의 길이를 누적합으로 저장한다.

for문에서 S의 각 원소가 홀수면 리스트 arr에 arr의 마지막 값을 다시 추가하고, 짝수면 arr의 마지막 값을 1 증가시킨다.

 

arr의 K 번째 원소까지는 앞의 홀수 원소들을 모두 제거할 수 있으므로 그 마지막 값을 결과값 res에 저장한다.

for문에서 K개의 홀수 원소를 제거한 짝수로 이루어진 수열 길이의 최댓값으로 res를 갱신해 나간다.

arr의 길이 M이 K보다 작다면 결과값 res에는 누적합의 최댓값이 저장되고, for문은 실행되지 않는다.

 

def solution():
    N, K = map(int, input().split())
    S = list(map(int, input().split()))
    arr = [0]
    for i in range(N):
        if S[i]%2:
            arr.append(arr[-1])
        else:
            arr[-1] += 1
    res = arr[:K+1][-1]
    M = len(arr)
    for i in range(K+1, M):
        if arr[i]-arr[i-(K+1)] > res:
            res = arr[i]-arr[i-(K+1)]
    print(res)

solution()