[백준 22857번] 파이썬 - 가장 긴 짝수 연속한 부분 수열(small)

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

시간 제한 1초, 메모리 제한 1024MB

# 조건

• 길이가 $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번 원소를 삭제한 수열에서 짝수로 이루어져 있는 연속한 부분 수열 중 가장 긴 길이를 출력한다.

# 접근 방법

• N의 제한이 50000이고, K의 제한은 100이다.
• 따라서 모든 경우의 수를 완전 탐색으로 살펴본다면 TL를 받게 된다.
• 이전의 결과 값을 사용하기 위하여 DP를 활용해준다.
• 최대 k번 지울 수 있으므로 2차원 크기가 k+1이고, 1차원의 크기가 N+1인 DP를 생성해준다.
• 이후 입력받은 숫자를 k번씩 순회하며 순회하며 짝수인 경우 dp[i-1][j] + 1을 해준다
  • k를 소모하지 않았으므로 직전 값의 지운 횟수에서 + 1
• 홀수인 경우 dp[i-1][j-1]을 해준다.

import sys  
sys.stdin = open('input.txt')  
si = sys.stdin.readline  

N, K = map(int, si().split())  
nums = [0] + list(map(int, si().split()))  
dp = [[0] * (K+1) for _ in range(N+1)]  
for i, j in enumerate(nums):  
    if not i:  
        continue  
    for k in range(K+1):  
        if not j % 2:  
            dp[i][k] = dp[i-1][k] + 1  
        elif k != 0 and j % 2:  
            dp[i][k] = dp[i-1][k-1]  
result = 0  
for i in dp:  
    temp = max(i)  
    result = max(result, temp)  
print(result)

• 아래와 같이 투 포인터로도 풀어줄 수 있다.
• right 포인터가 짝수인 경우 현재 짝수 카운트 +1, right + 1, result 갱
• 아닌 경우, 현재 K가 남아있다면 K-=1, right +=1
• K가 없다면, 현재 left 포인터가 짝수이면 now -= 1, 아니라면 K += 1을 하고 left += 1을 해준다.

# https://www.acmicpc.net/problem/22857

import sys

input = sys.stdin.readline


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

left, right = 0, 0
ans, now = 0, 0
while right < N:
    if arr[right] % 2 == 0:
        now += 1
        right += 1
        ans = max(ans, now)
    else:
        if K:
            K -= 1
            right += 1
        else:
            if arr[left] % 2 == 0:
                now -= 1
            else:
                K += 1
            left += 1

print(ans)