문제 링크 (opens new window)

초기 풀이

1. Set 자료구조 써서 K 소비한 배열 정보를 그대로 담도록 구현했었음.
2. 메모리 초과

import Foundation

let NK = readLine()!.split(separator: " ").map { Int($0)! }; let N = NK[0]; let K = NK[1]
let S = readLine()!.split(separator: " ").map { Int($0)! }

var dp: [Set<[Int]>] = .init(repeating: .init(), count: K + 4)
var ret = Int.min

func even(_ array: [Int]) -> Int {
    var count = 0
    var ret = 0
    for i in array {
        if i % 2 == 0 {
            count += 1
        } else {
            ret = max(count, ret)
            count = 0
        }
    }

    return count
}
dp[0] = .init(arrayLiteral: S)
for i in 1...K {
    for sub in dp[i-1] {
        for elem in sub {
            dp[i].insert(sub.filter({ elem != $0 }))
        }
    }

    for sub in dp[i] {
        ret = max(ret, even(sub))
    }
}

print(ret)

풀이

1. 풀이 이전에 연속된 짝수 갯수 계산을 위해서는 K개만큼 홀수 숫자를 삭제해야 함을 알아야 한다.
2. go 함수에 전달하는 index파라미터 기준으로 소모한 K 갯수를 가지고 분기처리를 진행한다.
3. 현재 인덱스값이 짝수인 경우 length + 1로 재귀호출
4. 홀수인 경우 k 하나 소모해서 다음 인덱스로 넘어가기
5. k 소모 갯수가 한계치 K값과 동일한 경우 재귀 멈추고 리턴
6. 전체 인덱스마다 K를 0부터 K까지 증가시켜가면서 맥스값을 최종 리턴

import Foundation

let NK = readLine()!.split(separator: " ").map { Int($0)! }; let N = NK[0]; let K = NK[1]
let S = readLine()!.split(separator: " ").map { Int($0)! }
var dp: [[Int]] = .init(repeating: .init(repeating: 0, count: K+4), count: N+4)
var ret = Int.min

if N == 1 {
    if S[0] % 2 == 0 {
        print(1)
    } else {
        print(0)
    }
    exit(0)
}

func go(_ k: Int, _ index: Int, _ length: Int) -> Int {
    if k > K || index < 0 { return length } // 소모한 k 갯수가 주어진 K보다 크면 전부 소모한 것
    if dp[index][k] != 0 { return length } // index까지 k개 소모한 갯수 계산이 이미 이루어졌으면 갯수 리턴, 중복 줄이기

    var value = 0
    if S[index] % 2 == 0 {
        value = go(k, index-1, length+1)
    }
    else if k == K { return length } // k 완전히 소모한 경우
    else if k < K {
        value = go(k + 1, index - 1, length) // 현재 인덱스값 홀수이면서 소모
    }
    dp[index][k] = value
    return dp[index][k]
}
for i in (1...N-1).reversed() {
    for j in 0...K {
        ret = max(go(j, i, 0), ret)
    }
}
print(ret)