[Swift 백준] 1965 상자넣기

 

 

풀이 아이디어

dp 문제입니다.

점화식을 구해야하는데,

마지막 상자가 어떤것일때 몇개인지 를 구하면 됩니다

 

dp[i]: i번째 상자를 마지막으로 포함할 때 넣을 수 있는 상자의 최대 개수

• 예를 들어, 상자 크기가 1, 2, 3, 5, 4라고 할 때:
  • dp[0] = 1 (상자 1 하나만 포함)
  • dp[1] = 2 (상자 1, 2 포함)
  • dp[2] = 3 (상자 1, 2, 3 포함)
  • dp[3] = 4 (상자 1, 2, 3, 5 포함)
  • dp[4] = 3 (상자 1, 2, 4 포함)

자세한 과정은 주석과 추가 설명을 덧붙이겠습니다.

풀이

import Foundation

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

// dp 배열 초기화 ( 모든 상자는 자기 자신 하나만을 포함할 수 있어서 1로 초기화)
var dp = Array(repeating: 1, count: n)

// 점화식 계산
for i in 1..<n {              // i번째 상자까지 탐색
    for j in 0..<i {          // i보다 앞에 있는 상자들 탐색
        if input[j] < input[i] {       // 앞의 상자가 현재 상자보다 작을 경우
            dp[i] = max(dp[i], dp[j] + 1) // j번째 상자까지 포함한 경우를 고려
        }
    }
}

// 결과 출력: dp 배열의 최대값
print(dp.max()!)

1. dp[j]는 j번째 상자를 포함했을 때 넣을 수 있는 상자의 최대 개수를 의미합니다.
   • 즉, j번째 상자를 마지막으로 포함했을 때 몇 개의 상자가 들어갈 수 있는지 알려주는 값입니다.
2. dp[j] + 1은 j번째 상자 이후에 i번째 상자를 추가했을 때 넣을 수 있는 상자의 개수입니다.
   • dp[j]는 j번째 상자까지의 최대 상자 개수를 의미하고,
   • + 1은 현재의 i번째 상자를 추가한 것이므로 1을 더해줍니다.
3. max(dp[i], dp[j] + 1)는 현재 i번째 상자를 포함할 경우의 최대 개수를 갱신합니다.
   • 이미 계산된 dp[i] 값과 dp[j] + 1 값을 비교해서 더 큰 값을 선택합니다.
   • 즉, i번째 상자를 포함했을 때 더 많은 상자를 넣을 수 있다면 dp[i]를 업데이트하는 것입니다.

 

 

 

 

 

번외로, 증가하는 수열에 대한 문제이기때문에 개인적으론 for문을 역순으로 순회 하는게 가독성이 더 좋다고 생각합니다.

 

풀이 with reversed

import Foundation

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

var dp = Array(repeating: 1, count: n)

for i in (0..<n).reversed() {
    for j in i + 1..<n {
        if input[i] < input[j] {
            dp[i] = max(dp[i], dp[j] + 1)
        }
    }
}

print(dp.max()!)