99클럽 코테 스터디 4기 30일차 TIL - 백준: 상자넣기(1965) Swift & Python

ℹ️ 문제 정보

플랫폼	번호	제목	유형	난이도	언어
백준	1965	상자넣기	DP	실버2	Swift, Python

🚀 나의 접근 방법

지금 상자에 앞(왼쪽)에 상자들이 몇 개 들어올 수 있는지 확인하면 된다.

하지만 그냥 계산하면 중복 연산이 많기 때문에 DP(다이나믹 프로그래밍)을 사용한다.

dp 테이블을 정의하고 상자를 차례로 접근한다. 현재 접근 중인 상자 앞(왼쪽)에 현재 상자 크기 보다 작은게 있다면 그 상자(작은 상자)의 dp 값에 1을 더한다.

앞에 작은 상자가 여개 일 수도 있으니 모두 같은 연산을 하고 그중 최댓값을 현재 dp에 저장한다.

그리고 dp 테이블에서 최댓값을 찾으면 답이 된다.

✍️ 나의 코드

Swift

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

var dp: [Int] = Array(repeating: 0, count: N)
for i in stride(from: 0, to: N, by: 1) {
    var max = 1
    for j in stride(from: 0, to: i, by: 1) {
        if nums[i] > nums[j] {
            let num = dp[j]+1
            if max < num { max = num }
        }
    }
    dp[i] = max
}

print(dp.max()!)

Python

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

dp = [0] * n
for i in range(n):
    maxNum = 1
    for j in range(0, i):
        if nums[i] > nums[j]:
            num = dp[j] + 1
            if num > maxNum: maxNum = num
    dp[i] = maxNum

print(max(dp))

🤔 회고

오늘도 해결하기 쉬운 문제가 나왔다.