문제 풀이
DP
prev = 무기마다 이전 회차까지 클리어하는 최소 시간
cur = 무기마다 현재 회차까지 클리어하는 최소 시간
min1 = 이전 회차까지 클리어하는 최소 시간 중 최솟값
minIdx = 이전 회차까지 클리어하는 최소 시간이 최솟값인 무기
min2 = 이전 회차까지 클리어하는 최소 시간 중 최솟값 다음으로 가장 작은 값
현재 회차까지 클리어하는 최소 시간을 구하는 방법은 무기마다 현재 회차의 클리어 시간과 해당 무기를 제외한 나머지 무기들 중 이전 회차까지 클리어하는 최소 시간을 더한 값을 구하고 최솟값을 찾는 것임
이에 따라 매번 해당 회차까지 클리어하는 최소 시간을 무기마다 구하면 됨
이때 해당 무기를 제외한 나머지 무기들 중 이전 회차까지 클리어하는 최소 시간을 구해야 하는데 최솟값이 되는 무기가 있다고 하면 그 무기만 이번 회차에서 사용할 수 없는 것이므로 해당 무기를 사용한 현재 회차는 이전 회차 클리어 시간 중 최소 시간 다음으로 빠른 시간을 더해주면 됨
매번 현재 회차까지의 최소 클리어 시간을 cur에 구해서 저장하고 나면 다음 회차를 계산할 때는 이 시간이 이전 회차가 되므로 prev에 저장하면 됨
N회차까지 반복하면 prev에 무기마다 N회차까지 클리어하는 최소 시간이 저장되어 있으므로 이 중 최솟값을 출력하면 정답
풀이 설명
각 회차에 무기마다 클리어 시간이 주어진다. 직전 회차에 쓴 무기를 쓸 수 없다고 할 때 가장 빠르게 N회차를 클리어하는 시간을 구하는 문제이다.
N회차까지 클리어하는 최소 시간은 N - 1회차까지 클리어하는 최소 시간에 현재 회차의 클리어 시간을 더해 구하기 때문에 문제를 DP로 풀 수 있다.
이 방법으로 문제를 풀기 위해 무기마다 이전 회차까지 최소 클리어 시간을 저장하기 위한 배열 prev, 현재 회차까지 최소 클리어 시간을 저장하기 위한 배열 cur를 만든다.
첫 회차는 해당 무기로 클리어하는 시간이 최소 클리어 시간이므로 그대로 prev 배열에 클리어 시간을 저장한다.
다음 회차부터는 cur 배열에 먼저 해당 무기로 클리어하는 시간을 저장하고 해당 무기를 제외한 다른 무기를 사용해 이전 회차까지 클리어한 최소 시간을 구해서 더해야 한다.
이 때 다른 무기를 사용해 이전 회차까지 클리어한 최소 시간을 무기마다 구할 필요가 없이 이전 회차까지 클리어한 시간이 최소인 무기와 최솟값을 찾아놓으면 해당 무기를 제외한 다른 무기의 클리어 시간에는 최솟값을 더하면 된다.
그리고 최솟값이 되도록 만드는 무기는 해당 무기를 제외한 무기들 중 이전 회차까지 최소 클리어시간이 가장 작은 시간을 더해야 하므로 전체에서 두 번째로 작은 최소 클리어시간을 미리 구해놓으면 편하다.
이 방식으로 매번 현재 회차까지 최소 클리어 시간을 cur에 저장해놓으면 다음 회차를 구할때는 이 값들이 이전 회차가 되므로 prev에 현재 배열을 저장하고 현재 회차의 클리어 시간을 구할때 배열 안에 값을 덮어 씌우기 때문에 원래 prev에 저장된 배열을 재사용할 수 있으므로 cur와 prev의 배열을 서로 바꾸어 준다.
이렇게 N회차까지 반복하면 prev에 무기마다 N회차까지 클리어하는 최소 시간이 저장되므로 이 값들 중 최솟값을 찾아서 출력하면 정답이 된다.
소스 코드
import java.io.StreamTokenizer
fun main() = StreamTokenizer(System.`in`.bufferedReader()).run {
fun nextInt(): Int{
nextToken()
return nval.toInt()
}
val N = nextInt()
val M = nextInt()
var prev = IntArray(M){nextInt()}
var cur = IntArray(M)
repeat(N - 1){
var min1 = Int.MAX_VALUE
var min2 = Int.MAX_VALUE
var minIdx = 0
for(i in 0 until M){
if (prev[i] < min1) {
min2 = min1
min1 = prev[i]
minIdx = i
} else if (prev[i] < min2) {
min2 = prev[i]
}
}
for(i in 0 until M){
cur[i] = nextInt() + if(i == minIdx) min2 else min1
}
prev = cur.also { cur = prev }
}
println(prev.min())
}