https://www.acmicpc.net/problem/22862
22862번: 가장 긴 짝수 연속한 부분 수열 (large)
수열 $S$에서 최대 $K$번 원소를 삭제한 수열에서 짝수로 이루어져 있는 연속한 부분 수열 중 가장 긴 길이를 출력한다.
www.acmicpc.net
투포인터 문제다.
풀이
짝수가 연속된 수열에서 k번의 삭제를 할 수 있다는 얘기는 최대 k개의 홀수가 담긴 배열의 크기를 찾는 것과 같은 이야기다. 구간의 범위를 나타내는 head와 tail 변수를 사용하여 탐색한다.
구간 안에 홀수가 k개 이하라면 tail을 증가시켜 구간을 늘린다. 매 탐색마다 구간의 크기는 (tail - head - 홀수의 개수)가 된다. 해당 부분의 최댓값을 출력하면 정답이다.
구간의 범위를 나타내는 head와 tail 변수를 사용하여 범위를 탐색, 구간 안에 홀수가 k개를 초과한다면, head를 증가시켜 구간을 축소시켜 홀수의 개수를 조절한다. tail이 이미 N이라면, 더 이상 증가시킬 수 없다는 뜻이므로 반복문 종료.
정답 코드
'Problem Solving > BOJ' 카테고리의 다른 글
| [12892] 생일 선물 (0) | 2023.01.21 |
|---|---|
| [6137] 문자열 생성 (0) | 2023.01.20 |
| [1484] 다이어트 (0) | 2023.01.18 |
| [2118] 두 개의 탑 (0) | 2023.01.17 |
| [1652] 누울 자리를 찾아라 (0) | 2023.01.16 |