문제 이해하기
숫자로 이루어진 리스트 nums와 정수 k가 주어질 때, 최소 k개의 홀수를 포함하는 가장 긴 증가 부분 수열의 길이를 구해야 합니다.
예를 들어 입력이 다음과 같다고 가정해 보겠습니다.
- nums = [12, 14, 16, 5, 7, 8]
- k = 2
홀수가 2개 이상 포함된 가장 긴 증가 부분 수열은 [5, 7, 8]이므로, 출력 결과는 3이 됩니다.
풀이 접근법
이 문제는 재귀 호출을 활용한 동적 프로그래밍(DP) 방식으로 해결할 수 있습니다. 핵심 아이디어는 각 위치에서 현재 숫자를 부분 수열에 포함하거나 건너뛰는 두 가지 선택지를 모두 탐색하면서, 지금까지 만난 홀수의 개수를 함께 추적하는 것입니다.
구체적인 단계는 다음과 같습니다.
best := 0 으로 초기화합니다.
dp() 함수를 정의합니다. 매개변수는 i, j, odd, taken 입니다.
odd >= k 라면, best := max(best, taken) 을 수행합니다.
j가 nums의 크기와 같다면 함수를 종료(return)합니다.
nums[j] > nums[i] 라면, dp(j, j + 1, odd + (nums[j] & 1), taken + 1) 을 호출하여 현재 숫자를 포함하는 경우를 탐색합니다.
dp(i, j + 1, odd, taken) 을 호출하여 현재 숫자를 건너뛰는 경우도 함께 탐색합니다.
메인 로직에서는 모든 시작 인덱스에 대해 dp(i, i + 1, nums[i] & 1, 1) 을 호출합니다.
최종적으로 best를 반환합니다.
구현 예제
아래 파이썬 코드를 통해 더 잘 이해할 수 있습니다.
class Solution: def solve(self, nums, k): best = 0 def dp(i, j, odd, taken): nonlocal best if odd >= k: best = max(best, taken) if j == len(nums): return if nums[j] > nums[i]: dp(j, j + 1, odd + (nums[j] & 1), taken + 1) dp(i, j + 1, odd, taken) for i in range(len(nums)): dp(i, i + 1, nums[i] & 1, 1) return best ob = Solution() nums = [12, 14, 16, 5, 7, 8] k = 2 print(ob.solve(nums, k))
입력
[12, 14, 16, 5, 7, 8], 2
출력
3
동작 원리
위 코드는 세 가지 상태를 추적합니다. 첫째, 마지막으로 선택한 요소의 인덱스 i, 둘째, 검토 중인 요소의 인덱스 j, 셋째, 지금까지 발견한 홀수의 개수 odd입니다. 비트 연산자 &를 활용한 nums[j] & 1 표현식은 숫자가 홀수이면 1, 짝수이면 0을 반환하므로 홀짝 여부를 빠르게 판별할 수 있습니다. 모든 가능한 경로를 재귀적으로 탐색한 후, 홀수가 k개 이상인 경로 중 가장 긴 수열의 길이가 best 변수에 저장되어 최종적으로 반환됩니다.