DynamicProgramming_1_12_가장 긴 짝수 연속한 부분 수열 (small) (22857) 모루겠음!!

Eugenius1st·2022년 4월 9일

Algorithm_Baekjoon

목록 보기

63/158

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

문제

길이가 $N$ 인 수열 $S$ 가 있다. 수열 $S$ 는 1 이상인 정수로 이루어져 있다.
수열 $S$ 에서 원하는 위치에 있는 수를 골라 최대 $K$ 번 삭제를 할 수 있다.

예를 들어, 수열 $S$ 가 다음과 같이 구성되어 있다고 가정하자.

수열 S : 1 2 3 4 5 6 7 8
수열 $S$ 에서 4번째에 있는 4를 지운다고 하면 아래와 같다.

수열 S : 1 2 3 5 6 7 8
수열 $S$ 에서 최대 $K$ 번 원소를 삭제한 수열에서 짝수로 이루어져 있는 연속한 부분 수열 중 가장 긴 길이를 구해보자.

입력

수열 $S$ 의 길이 $N$ 와 삭제할 수 있는 최대 횟수인 $K$ 가 공백으로 구분되어 주어진다.
두 번째 줄에는 수열 $S$ 를 구성하고 있는 $N$ 개의 수가 공백으로 구분되어 주어진다.

출력

수열 $S$ 에서 최대 $K$ 번 원소를 삭제한 수열에서 짝수로 이루어져 있는 연속한 부분 수열 중 가장 긴 길이를 출력한다.

풀이

투포인터로 해결할 가능.
while문은 end를 한 칸씩 뒤로 이동시켜주기 위한 반복문이다. 홀수의 갯수cnt가 k개 이하이고 end가 n-1 이하라면 계속 실행된다.

현재 수가 홀수일 때
홀수의 갯수cnt가 이미 k개라면 이번 수를 부분수열에 넣어줄 수 없으므로 반복문을 탈출한다. k개가 아니라면 부분수열에 넣어줄 수 있으므로 cnt를 1 늘려주고 현재 부분수열의 길이size를 1 늘려준다.
현재 수가 짝수일 때
현재 부분수열의 길이size를 1 늘려준다.
end가 n-1이 되면 더이상 end += 1 작업을 할 수 없도록 막기 위해 플래그를 0으로 바꿔주고 반복문을 탈출한다. end가 아직 n-1이 아니라면 한 칸 뒤로 이동시켜준다.
반복문을 탈출하면 부분수열의 길이size에서 홀수의 갯수cnt를 빼 짝수 부분수열의 길이를 구한다. 그리고 이것이 가장 긴 짝수 부분수열이라면 size_max를 업데이트해준다.
이제 더이상 end를 뒤로 이동시킬 수 없으므로 start를 뒤로 이동시킬 것이다. 그러기 위해 현재 부분수열에서 현재 start 포인터가 가리키는 수를 제외시켜야 한다. 현재 수가 홀수라면 cnt를 1 감소시키고, size도 1 감소시킨다. 짝수일 경우 size만 1 감소시킨다.

start: 부분수열의 시작 포인터
end: 부분수열의 끝 포인터
cnt: 현재 부분수열의 홀수의 갯수
size: 현재 부분수열의 길이
size_max: 가장 긴 짝수 부분수열의 길이
flag: end가 n-1이 되면 더이상 end += 1 작업을 할 수 없도록 막기 위한 플래그

코드

import sys
input = sys.stdin.readline

n, k = map(int, input().split())
lst = list(map(int, input().split()))

cnt = 0
start, end = 0, 0
size, size_max = 0, 0
flag = 1

for start in range(n):
    while cnt <= k and flag:
        if lst[end] % 2:
            if cnt == k:
                break
            cnt += 1
        size += 1
        if end == n - 1:
            flag = 0
            break
        end += 1
        
    if size_max < size - cnt:
        size_max = size - cnt
        
    if lst[start] % 2:
        cnt -= 1
        
    size -= 1

print(size_max)