22862번: 가장 긴 짝수 연속한 부분 수열 (large)
수열 $S$에서 최대 $K$번 원소를 삭제한 수열에서 짝수로 이루어져 있는 연속한 부분 수열 중 가장 긴 길이를 출력한다.
www.acmicpc.net
문제
길이가 인 수열 가 있다. 수열 는 1 이상인 정수로 이루어져 있다.
수열 에서 원하는 위치에 있는 수를 골라 최대 번 삭제를 할 수 있다.
예를 들어, 수열 가 다음과 같이 구성되어 있다고 가정하자.
수열 S : 1 2 3 4 5 6 7 8
수열 에서 4번째에 있는 4를 지운다고 하면 아래와 같다.
수열 S : 1 2 3 5 6 7 8
수열 에서 최대 번 원소를 삭제한 수열에서 짝수로 이루어져 있는 연속한 부분 수열 중 가장 긴 길이를 구해보자.
입력
수열 의 길이 와 삭제할 수 있는 최대 횟수인 가 공백으로 구분되어 주어진다.
두 번째 줄에는 수열 를 구성하고 있는 개의 수가 공백으로 구분되어 주어진다.
출력
수열 에서 최대 번 원소를 삭제한 수열에서 짝수로 이루어져 있는 연속한 부분 수열 중 가장 긴 길이를 출력한다.
코드
n, k = map(int, input().split())
arr = list(map(int, input().split()))
start, end = 0, 0
num_odd = 0
ans = 0
while end < n:
if num_odd <= k:
if arr[end] % 2 == 1: # end의 값이 홀수라면
num_odd += 1
end += 1
else:
if arr[start] % 2 == 1:
num_odd -= 1
start += 1
ans = max(ans, end-start-num_odd)
print(ans)
이전에 DP로 풀이한 적이 있는 문제이다. 위와 같이 투포인터로도 해결이 가능하다.
- 앞에서부터 배열의 길이를 조금씩 늘려가며 배열 안의 원소를 최대 K번 삭제했을 때 가장 긴 짝수 연속한 부분 수열을 찾는다. 배열에서 짝수 연속한 부분 수열이 되려면 홀수를 최대 K번 지우면 짝수만 남는 수열이면 된다.
- 배열의 길이를 늘리며 새로 추가되는 원소가 홀수인지 살펴본다. 홀수이면 num_odd를 1 증가시켜서 홀수의 개수를 세준다.
- num_odd가 K개를 넘으면 현재 start 인덱스의 arr 값이 홀수인지 살펴보고 홀수라면 num_odd를 1 감소시킨다. 그리고 start를 1 증가시켜준다.
위 과정을 end가 n보다 작은동안 반복하여 가장 긴 짝수 연속한 부분 수열의 길이를 구하여 준다.
'문제풀이 > 투포인터' 카테고리의 다른 글
[Python/파이썬] 백준 17609번 회문 (0) | 2023.03.26 |
---|---|
[Python/파이썬] 백준 15961번 회전 초밥 (0) | 2023.02.17 |
[Python/파이썬] 백준 2470번 두 용액 (0) | 2023.02.17 |
[Python/파이썬] 백준 11728번 배열 합치기 (0) | 2023.02.16 |
[Python/파이썬] 백준 2473번 세 용액 (1) | 2022.09.13 |