[99클럽 코테 스터디 28일차 TIL] 가장 큰 증가하는 부분 수열 - 백준 11055

LIS 변형 문제가 나왔다.

 

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

수열 A가 주어졌을 때, 그 수열의 증가하는 부분 수열 중에서 합이 가장 큰 것을 구하는 프로그램을 작성하시오.
예를 들어, 수열 A = {1, 100, 2, 50, 60, 3, 5, 6, 7, 8} 인 경우에
합이 가장 큰 증가하는 부분 수열은 A = {1, 100, 2, 50, 60, 3, 5, 6, 7, 8} 이고,
합은 113이다.

[입력]
첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000)이 주어진다.
둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000)

[출력]
첫째 줄에 수열 A의 합이 가장 큰 증가하는 부분 수열의 합을 출력한다.

풀이 접근

가장 긴 증가하는 수열(Longest Increasing Subsequence; LIS)를 변현해서 풀었다.

LIS가 길이라면, 이 문제는 합을 구하면 된다.

따라서 DP Table은 각 요소자체로 초기화 한다.

var dp = nums

그리고 길이 값을 갱신하는 대신 합의 최대값으로 갱신한다.

dp[i] = max(dp[i], dp[j] + nums[i])

최종 코드 - Swift

let n = Int(readLine()!)!
let nums = readLine()!.split(separator: " ").map{ Int("\($0)")! }
var dp = nums
for i in 1..<n {
    for j in 0..<i {
        if nums[i] > nums[j] {
            dp[i] = max(dp[i], dp[j] + nums[i])
        }
    }
}
print(dp.max()!)

Conclusion

동적계획법 어렵다...