22857 가장 긴 짝수 연속한 부분 수열 (small)

1. 문제

문제는 링크에 들어가면 있다.

2. 정답 코드

문제의 내 정답 코드는 다음과 같다.

import sys
read = sys.stdin.readline

N,K = map(int,read().split())
array = list(map(int,read().split()))

# 이 문제는 슬라이딩윈도우 문제인거 같은데
# 일단 값을 하나씩 먹어가면서 최대 길이를 저장하자.
# 다음 값을 확인했을 때, 최대 길이가 갱신된다면, 교체하는 느낌.

# 먼저 시작 지점을 찾자.
max_val = 0
for start,a in enumerate(array) :
    if a % 2 == 0 :
        max_val = 1
        break

from collections import deque
temp_window = deque([a])

count = 0
for aa in range(start+1,len(array)) :
    now = array[aa]
    if now % 2 == 1 :
        # K가 0인데 홀수를 만나면 현재 홀수를 추가하고
        # 앞에 K가 홀수인 것을 뺄때까지 pop하기.
        if K - count <= 0 :
            while K-count <= 0:
                temp_val = temp_window.popleft()
                if temp_val % 2 == 1 :
                    count -= 1
                else :
                    continue
        count += 1
        # 깎고 temp_window에 일단 추가
        temp_window.append(now)
    else :
        temp_window.append(now)

    max_val = max(max_val,len(temp_window)-count)
    # print(count,temp_window,max_val)
print(max_val)

3. 풀이 및 생각

문제 풀이

이 문제를 나는 슬라이딩 윈도우로 플었다. 그 이유는 모든 경우를 확인해야 했기 때문이다. dp를 어떻게 쓰는지는 모르겠지만, 슬라이딩 윈도우로 푸는 것이 가장 합당하다고 판단했다.

핵심은 시작점을 찾고, max_val을 저장한 후, 슬라이딩 윈도우로 훑으면서 홀수를 만났을 때 대처하는 방법을 잘 풀어내는 것이다. 나는 그래서 홀수를 만나면 K가 고정되어있으니, 현재 만난 홀수를 배열에 넣기 위해서 queue의 왼쪽에 홀수가 빠져나올 때까지 popleft를 해주었다. 이런 식으로 해서 매번 max_val을 비교한다.

나의 생각

아무리봐도 dp로 풀 각이 안보이는데.. 왜 dp로 분류되는진 모르겠다. 슬라이딩 윈도우가 여기저기 쓰이는데, 배워뒀다는 것에 대해 꽤 뿌듯하다.