[코딩테스트] 🔌 전깃줄 - 백준 2565

문제링크

난이도

골드 5

유형

DP, LIS

소요시간

1시간

회고

DP 문제도 이번 챌린지 들어서 처음이고, LIS 알고리즘도 몰라서 어려웠다. 인접 배열간에 수열이 만들어지면 카운트를 했는데, 인접 배열이 아닌, 전체 배열에서 증가 수열을 구해야했다.

코드

let N = Int(readLine()!)!

var graph = Array(repeating: 0, count: 501)

(0..<N).forEach { _ in
    let row = readLine()!.split(separator: " ").map { Int($0)! }
    graph[row[0]] = row[1]
}

let dest = graph
    .enumerated()
    .filter { $0.element != 0 }
    .sorted { $0.0 < $1.0 }
    .map { ($0.element) }

var dp = Array(repeating: 1, count: dest.count)

print(dest)

for i in 0..<dest.count {
    for j in 0..<i {
        if dest[i] > dest[j] {
            dp[i] = max(dp[i], dp[j] + 1)
        }
    }
}

print(N - dp.max()!)