99클럽 코테 스터디 4기 31일차 TIL - 백준: 줄세우기(2631) Swift & Python

ℹ️ 문제 정보

플랫폼	번호	제목	유형	난이도	언어
백준	2631	줄세우기	DP	골드4	Swift, Python

🚀 나의 접근 방법

이 문제는 결국 가장 긴 증가하는 부분 수열 찾기이다!

이미 오름 차순으로 정렬된 번호는 그대로 두고 나머지 번호들을 옮기면 된다.

그래서 가장 긴 증가하는 부분 수열의 길이를 찾아 N에서 빼주면 답이 된다.

✍️ 나의 코드

Swift

let N = Int(readLine()!)!
var people: [Int] = []
for _ in 0..<N {
    people.append(Int(readLine()!)!)
}

var dp: [Int] = Array(repeating: 1, count: N)
for i in 0..<N {
    for j in 0..<i {
        if people[i] > people[j] {
            dp[i] = max(dp[i], dp[j] + 1)
        }
    }
}

print(N - dp.max()!)

Python

N = int(input())
people = []
for _ in range(N):
    people.append(int(input()))

dp = [1] * N
for i in range(N):
    for j in range(i):
        if people[i] > people[j]:
            dp[i] = max(dp[i], dp[j] + 1)

print(N - max(dp))

🤔 회고

핵심만 캐치 했으면 아주 쉽게 해결할 수 있는 문제였다. 하지만 빠르게 캐치하지 못해서 아쉽다. 더 많은 문제를 경험해 보자!