BOJ 22857 [가장 긴 짝수 연속한 부분 수열]

문제

2022-02-25

문제 보기

장욱이가 스터디에서 어렵다고한 문제이다.

아이디어

[1,2,1,2,1,2,1,1,1,1,2,2,2,2,2] 같은 수열에서 k개의 홀

수를 제거할때 짝수가 가장 많이 연속되게 하는 경우 연속된 짝

수의 수를 구하는 문젠데 '제거하는 홀수는 모두 정답에 들어가

는 짝수와 붙어있다'가 1번 아이디어였고 2번 아이디어는 n^2

로 풀면 되니까 for문으로 첨부터 끝까지 홀수를 k개만큼 각각

제거해서 짝수를 세는 법을 해봤는데 시간 초과가 됐다.

투포인터를 써서 시간 초과 없이 풀 수 있었다.

투 포인터

참조할 두 index를 조절하면서 탐색하는 방법, front back

일 경우 해당 front에서 최대로 back을 늘려주고

answer과 max연산을 취한뒤 다음으로 탐색할 index로 front

를 이동시킨다.

-> 투 포인터 개념은 나중에 자세히 다루도록 하자.