[백준] (Swift) 11053번 - 가장 긴 증가하는 부분 수열 (DP로 푸는 LIS, 최장 증가 부분 수열 개념)

 

문제 링크

https://www.acmicpc.net/problem/11053

11053번: 가장 긴 증가하는 부분 수열

 

문제 풀이 IDEA

초반에 도대체 이게 무슨 소리야, 그냥 오름차순이면 수열이 되는거임? 라고 생각하며 의아했지만, 바로 그게 잘 이해한 거였다. 최장 증가 부분 수열 (LIS, Longest Increasing Subsequences) 라는 개념인데, 주어진 배열에서 오름차순으로 이루어진 수열 중, 가장 긴 길이를 갖는 수열(LIS)의 길이를 구하라는 문제였다. LIS 에 대한 개념은, 바로 직전에 공부하며 정리한 글을 보고 이해하길 바란다.

https://didu-story.tistory.com/236

[알고리즘] (Swift) 최강 증가 부분 수열 (LIS) 알고리즘 (DP, 동적계획법을 활용한 LIS)

 

이 문제는 LIS 개념을 구현할 수 있느냐? 는게 핵심이다. 나는 아래와 같이 문제를 풀었다. (사실상 LIS 개념과 동일)

• 입력받는 수열의 길이 n, 입력받는 수열 inputArray,  i번째 까지의 최장 수열 길이를 넣는 배열 dp
• 현재 비교하고 싶은 수열의 위치 i, 비교할 이전의 인덱스 번호 j (0부터 i까지)
• 현재 inputArray[i] 가 만약 3 이라면, inputArray[0], inputArray[1], inputArray[2] 와 비교해야하고, 비교 후 inputArray[3]값이 더 크다면 dp의 값에 +1 해주어야 한다.이 과정을 코드로 구현하면 아래와 같다.

 

소스코드

let n = Int(readLine()!)!
let inputArray = readLine()!.split(separator: " ").map { Int(String($0))! }
var dp: [Int] = []

for i in 0..<n {
    dp.append(1)
    for j in 0..<i+1 {
        if inputArray[j] < inputArray[i] {
            dp[i] = max(dp[i], dp[j]+1)
        }
    }
}

print(dp.max()!)

※ 마지막에 dp.max() 값은 옵셔널 값으로 반환되니까 주의하자!