목록백준 22857 C++ (1)

1일1알

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

포인터 두개 (start, end)를 이용해서 탐색을 하는데, start 인덱스의 원소가 짝수일 때만 검사하고, 홀수가 k+1 들어가있는 가장 작은 수열을 찾는다. ex) 수열 S가 1, 2, 3, 4, 5, 6, 7, 8, 9 이고 K가 2라면 처음 찾는 수열은 2, 3, 4, 5, 6, 7 일 것이다. 이 수열에서 짝수로만 이루어져있는 수열은 2, 4, 6 이고 길이는 end - start - (cnt - 1)로 구할 수 있다. cnt는 찾은 홀수의 개수이고 1을 cnt에서 빼주는 이유는 홀수를 k개가 아닌 k+1개를 찾았기 때문에 더 찾은 1개를 cnt에서 빼주는 것이다. 그리고 찾은 수열을 일단 유지하면서 start를 이동시키고 start 인덱스의 원소가 홀수면 cnt를 줄여준다. 두번째 경우는 ..
알고리즘 2022. 2. 18. 12:21
이전 Prev 1 Next 다음