99클럽 코테 스터디 4기 27일차 TIL - 백준: 가장 긴 감소하는 부분 수열(11722) Swift

ℹ️ 문제 정보

플랫폼	번호	제목	유형	난이도	언어
백준	11722	가장 긴 감소하는 부분 수열	DP	실버2	Swift

🚀 나의 접근 방법

수열에서 i번째 수 보다 0~(i-1)번째 수에서 더 큰 값이 있다면 해당 수의 부분 수열의 길이에 +1 해주면 된다.

DP 테이블을 N 길이 만큼 1로 초기화 한다. 1로 초기화 하는 이유는 부분 수열의 초소 길이가 자기 자신 1개이기 때문이다.

✍️ 나의 코드

Swift

let N = Int(readLine()!)!
var nums = readLine()!.split(separator: " ").map{ Int($0)! }

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

print(dp.max()!)

🤔 회고

어렵진 않은 문제인데 뭔가 기존에 풀었던 DP문제와 조금 달라 빠르게 풀지 못 했다. 조금 더 다양한 문제를 풀어보자.