[Swift/Python] 백준_가장 큰 증가하는 부분 수열(11055)

문제

 

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

11055번: 가장 큰 증가하는 부분 수열

 

 

풀이

 

result[k] 는 numbers의 k번째 원소까지 증가하는 부분수열의 합을 나타냄. 

 

즉, numbers[j]가 numbers[i]보다 작다는 것은 result[j]에 numbers[i]를 더할 수 있다는 얘기임. 이렇게 구하며 max값으로 result[i]로 바꿔주면 가장 큰 값으로 result[i]의 값이 정해짐.

 

마지막에 result의 max값을 출력해주면 됨.

 

Swift

import Foundation
let n = Int(readLine()!)!
let numbers = readLine()!.split(separator: " ").map { Int(String($0))! }
var result = Array(repeating: 0, count: n)
for i in 0..<n {
    result[i] = numbers[i]
    for j in 0...i {
        if numbers[j] < numbers[i] {
            result[i] = max(result[i], result[j] + numbers[i])
        }
    }
}
print(result.max()!)

 

Python

n = int(input())
numbers = list(map(int,input().split()))
result = [0] * n
for i in range(0,n):
    result[i] = numbers[i]
    for j in range(0,i+1):
        if numbers[j] < numbers[i]:
            result[i] = max(result[i],result[j] + numbers[i])
print(max(result))

 

 

_____________________________________________________________________________________________________

 

다른 언어도 같이 하면 좋을 것 같아서 파이썬으로 시작해봤는데 아직 모르겠음. swift를 그냥 옮겨두기만함. 아직 블로그에 작성 못한 문제가 너무 많음. 화잍ㅇ