99클럽 코테 스터디 4기 28일차 TIL - 백준: 가장 큰 증가하는 부분 수열(11055) Swift & Python

ℹ️ 문제 정보

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

🚀 나의 접근 방법

수열을 순서대로 방문해서 방문 중인 수 기준으로 왼쪽에 있는 수들 중 본인보다 작은 수의 dp 테이블 값에 본인 값(방문 중인 수)을 더해 본인 순서 dp 테이블에 저장하면 된다.

방문 중인 수 왼쪽에 작은 수가 여러 개 있으면 합이 가장 큰 것을 dp 테이블에 저장하면 된다.

그리고 dp 테이블에서 최댓값을 출력하면 된다.

✍️ 나의 코드

Swift

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

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

print(dp.max()!)

Python

N = int(input())
nums = list(map(int, input().split(" ")))

dp = [] + nums
for i in range(N):
    for j in range(0, i):
        if nums[j] < nums[i]:
            dp[i] = max(dp[i], dp[j]+nums[i])

print(max(dp))

🤔 회고

DP는 문제 풀이에 비해 설명하는 것이 어려운 것 같다. 누군가에게 알려준다고 생각하듯이 연습하자!