[Algorithm/BOJ] 18353 - 병사 배치하기 (DP) Swift

문제 풀이:

N명의 병사가 무작위로 나열되어 있다. 각 병사는 특정한 값의 전투력을 보유하고 있으며, 병사를 배치할 때는 전투력이 높은 병사가 앞쪽에 오도록 내림차순으로 배치를 하고자 한다. 다시 말해 앞쪽에 있는 병사의 전투력이 항상 뒤쪽에 있는 병사보다 높아야 한다.

또한 배치 과정에서는 특정한 위치에 있는 병사를 열외시키는 방법을 이용한다. 그러면서도 남아있는 병사의 수가 최대가 되도록 하고 싶다.

LIS에 대한 개념을 아는 상태라면 쉽게 풀 수 있는 문제이다. 

하지만 기본적인 LIS는 오름차순이고 문제에서는 내림차순으로 바꿔 풀어야 한다. 

또한, 최대로 남은 병사의 수를 구하는 것이기 때문에 N에서 제일 긴 감소하는 부분 수열의 길이를 빼줘야 한다.

 

아래 그림은 내림차순인 것을 제외하면 전 포스팅의 방식과 똑같기 때문에 설명은 생략한다.

 

코드:

import Foundation

func solution() -> Int {
    let n = Int(readLine()!)!
    let soldiers = readLine()!.split(separator: " ").map { Int(String($0))! }
    var dp = [Int](repeating: 1, count: n)
    
    for i in 1..<n {
        for j in 0..<i {
            if soldiers[j] > soldiers[i] {
                dp[i] = max(dp[i], dp[j]+1)
            }
        }
    }
    return n-dp.max()!
}

print(solution())

문제:

18353번: 병사 배치하기