[백준] 22857 가장 긴 짝수 연속한 부분 수열 (small)

문제

• 길이가 N인 수열 S는 1 이상인 정수로 이루어져 있다.
• 수열 S에서 원하는 위치의 수를 최대 K번 삭제할 수 있다.
• 짝수로 이루어져 있는 연속한 부분 수열 중 가장 긴 길이 구하기

 

• 1 <= N <= 50,000
• 1 <= K <= 100

 

풀이

• 연속 부분 수열이란 그 수열의 원소를 하나 이상 연속하여 선택한 부분 수열을 말한다.
• 투포인터 또는 DP로 풀 수 있는 문제

 

• 시작지점 start에 따라 최대 K개의 홀수를 가지는 가장 긴 수열의 길이 구하기

 

N, K = map(int, input().split())
sequence = list(map(int, input().split()))

cnt = 0                 # 부분 수열의 홀수 개수
start, end = 0, 0       # 부분 수열의 시작, 끝
size, size_max = 0, 0   # 부분 수열 길이, 부분 수열의 최대 길이
flag = 1                # 수열의 끝 도달

for start in range(N) :
    # 홀수의 개수가 K개 이하이고 수열의 끝에 도달하기 전까지 반복
    while cnt <= K and flag :
        if sequence[end] % 2 :  # 홀수일 때
            if cnt == K : break # 1) 더이상 제거 못하는 경우 stop
            cnt += 1            # 2) 아닌 경우 홀수 개수 늘리기
        size += 1

        if end == N-1 :         # 수열의 끝에 도달한 경우
            flag = 0
            break
        end += 1
    
    # 가장 긴 부분 수열의 길이랑 현재 부분수열 길이 비교
    if size_max < size - cnt :
        size_max = size - cnt
    
    # start 앞으로 한 칸 이동 -> 홀수였다면 홀수 개수 줄이기
    if sequence[start] % 2 :
        cnt -= 1
    size -= 1

print(size_max)

 

References

• 백준 오늘의 문제