[백준/Swift] 14728: 벼락치기 | PS일지

문제

14728번: 벼락치기

간단한 문제 요약

일정 시간 이상을 들이면 해당 단원의 시험을 맞을 수 있다고 가정했을 때(대박,,일정 시간 투자만 하면 된다니) 시험의 단원 개수와 시험까지 공부할 수 있는 총 시간이 주어졌을 때, 특정 단원을 공부할 수 있는 시간과 그 단원을 공부했을 때 배점이 최대가 되는 경우를 구하시오!

 

문제 풀이

시험까지 공부할 수 있는 총 시간이 10000 밖에 안되서 2차원 dp로 풀었습니다. 주어진 최대 시간까지!! 특정한 과목을 0개 ~ N 개 까지 선택하며 최대 점수를 기록해 나갔습니다.

 

(1...n).map{
    for j in (0...k) {
        cache[$0][j] = cache[$0-1][j]
        if j-items[$0-1].time >= 0 {
            cache[$0][j] = max(cache[$0-1][j - items[$0-1].time] + items[$0-1].value, cache[$0-1][j])
        }
    }
}

cache에는 특정 과목을 공부했을 때 얻을 수있는 최대 점수를 기록해 나갑니다.

 

(1...n) 까지 map은 특정 과목을 공부했을 때, 그리고 for j in (0...k) 루프는 공부할 수 있는 특정 최대 시간 j일 때 현재 공부중인 과목을 공부했을 때 if j - items[$0-1].time >= 0 남는 시간이 있다면, 현재 과목을 공부했을 때 items[$0-1].value 남는 시간만 큼 이전 과목들을 공부했을 때 얻은 최대 점수 cache[$0-1][j-itmes[$0-1].time]를 더한 값이 큰지 아니면 현재 과목을 공부하지 않았을 때의 이전 과목들로 공부했을 때의 최대 시간 cache[$0-1][j] 둘 중 뭐가 큰지를 비교했습니다.

 

한가지 의아했던 점은 원래 구현한 코드는

items.sort {$0.time < $1.time}
...
for j in (items[$0-1].time...k) { ... }

 

 

 

두 번째 포문의 시작이 해당 과목을 공부했을 때 시간부터 총 공부할 수 있는 최단 시작하는 것인데.. 어째서 이게 틀리는 건지... 뚜렷한 이유를 찾지 못했습니다 ㅠ;

 

 

이렇게 풀 수있는 방법이 있고 일차원 방법으로 풀 수 있는 방법이 있습니다. 하지만 이차원 루프를 순차적으로 실행하게 된다면

(과목1) 2 10 이런 경우가 있을 때 공부할 수 있는 특정 시간대가 4인 경우 이미 공부한 과목을 또 공부하게 되는 결과가 발생됩니다. 그래서 총 시간부터 0까지 역으로 구해야 합니다. 그렇게 해야 공부할 수 있는 특정시간대가 4에서 3, 2로왔을 때 이 경우에 이미 시간이 4있을 때 한번 들었던 과목1을 다시 사용하지 않습니다.( 값이 작기 때문 )

...
for j in stride(from:k,through: items[$0-1].time, by: -1) {
    cache[j] = max(cache[j-items[$0-1].time] + items[$0-1].value, cache[j])
}

 

코드

typealias Element = (time: Int, value: Int)
let nk = readLine()!.split{$0==" "}.map{Int(String($0))!}
let n = nk[0],k = nk[1]
var cache = Array(repeating: Array(repeating: 0, count: k+1), count: n+1)
var items: [Element] = (0..<n).map{ _ in
    let input = readLine()!.split{$0==" "}.map{Int(String($0))!}
    return (input[0],input[1])
}
(1...n).map{
    for j in (0...k) {
        cache[$0][j] = cache[$0-1][j]
        if j-items[$0-1].time >= 0 {
            cache[$0][j] = max(cache[$0-1][j - items[$0-1].time] + items[$0-1].value, cache[$0-1][j])
        }
    }
}
print(cache[n][k])