BOJ-11055 가장 큰 증가하는 부분 수열 Swift

문제

수열 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의 합이 가장 큰 증가하는 부분 수열의 합을 출력한다.

내가 푼 풀이

- dp[i] = i번 인덱스 까지의 가장 큰 부분 수열의 합으로 정의하자.

- i번째 인덱스까지의 부분수열중 가장 작은부분수열은 arr[i] 자기 원소 하나만 가졌을때이다.

- dp[i] = arr[i]의 초기값을 가진다.

- 1부터 i-1번째 원소중 i번째 원소보다 작은 원소가 j번째에 있을때,

- j번째까지의 가장 큰 부분수열의 합이 i번째 원소와 더했을때 arr[i]의 초기값보다 커야한다.

 

 

위의 예시로 주어진 수열을 dp로 구하면 다음과 같다.

idx	1	2	3	4	5	6	7	8	9	10
arr	1	100	2	50	60	3	5	6	7	8
dp	1	101	3	53	113	6	11	17	24	32

 

코드로 구현해보자.

import Foundation

// 배열 입력
let count = Int(readLine()!)!
var arr = readLine()!.split(separator: " ").map{ Int($0)! }
arr.insert(0, at: 0)
var dp = Array(repeating: 0, count: count+1)
var max = Int.min

// dp 입력
// dp[n] = n번째 인덱스까지의 가장 긴 부분수열의 합
for i in 1...count {
    dp[i] = arr[i]
    for j in 1..<i {
        if arr[j] < arr[i] && dp[i] < dp[j] + arr[i] {
            dp[i] = dp[j] + arr[i]
        }
    }
}

print(dp.max()!)