[백준][Kotlin]4883번 삼각 그래프

해당 문제는 DP 문제입니다.

 

저의 경우 처음에는 혹시나 싶어 다익스트라 방식으로 작성해 봤었지만 메모리 초과라는 문제가 발생하여 이중 for문을 돌리면서 해당 위치값을 저장하고 있는 map 과 값을 갱신 및 누적할 map 을 생성하여 해당 문제를 작성하였습니다.

 

누적되는 map의 값을 구하는 방식을 구하는 것은 쉬웠으나 통과를 하지 못하여 식을 잘못 구한 듯 싶어 수정을 몇번 하였었지만 통과하지 못하였었습니다. 그래서 코드가 진행되는 과정에서 중간중간 출력문을 이용하여 값의 변경에 대해서 추적을 하여 문제를 찾았습니다.

 

제가 처음에 고려하지 못했던 문제는 값을 갱신하는 map에 있어 row값이 1 일 때 해당 row에 해당하는 col을 갱신할 때 올바른 값이 들어가지 않는다는 것을 알게되어 수정을 하여 해당 문제를 통과 할 수 있었습니다.

 

개인적으로 알고리즘 문제들을 풀면서 잘 안풀리는 경우 출력문을 통해 값의 변경과정을 확인해야 된다는 것을 다시금 깨닫게 해주는 문제였던 것 같습니다.

 

하기는 통과한 코드와 제출 결과 입니다.

import java.io.BufferedReader
import java.io.BufferedWriter
import java.io.InputStreamReader
import java.io.OutputStreamWriter
import java.util.StringTokenizer

fun main(){
    val br = BufferedReader(InputStreamReader(System.`in`))
    val bw = BufferedWriter(OutputStreamWriter(System.out))

    var case = 1

    while(true){
        var st = StringTokenizer(br.readLine())
        var N = st.nextToken().toInt()
        if(N == 0) break

        val map = Array(N) { LongArray(3) }
        val resultMap = Array(N) { LongArray(3)}
        // 확인할 배열 세팅
        repeat(N){
            st = StringTokenizer(br.readLine())
            map[it][0] = st.nextToken().toLong()
            map[it][1] = st.nextToken().toLong()
            map[it][2] = st.nextToken().toLong()
        }

        resultMap[0][1] = map[0][1]
        resultMap[0][2] = map[0][1] + map[0][2]

        for(row in 1 .. N-1){
            for(col in 0 .. 2){

                if(col == 0){
                    if(row == 1){
                        resultMap[row][col] = resultMap[0][1] + map[1][0]
                        continue
                    }
                    resultMap[row][0] = resultMap[row-1][0] + map[row][0]
                    resultMap[row][0] = Math.min(resultMap[row][0], resultMap[row-1][1] + map[row][0])
                }

                if(col == 1){

                    resultMap[row][1] = resultMap[row][0] + map[row][1] // 좌측에서 오는 거
                    resultMap[row][1] = Math.min(resultMap[row][1], resultMap[row-1][1] + map[row][1])
                    resultMap[row][1] = Math.min(resultMap[row][1], resultMap[row-1][2] + map[row][1])
                    if(row != 1) resultMap[row][1] = Math.min(resultMap[row][1], resultMap[row-1][0] + map[row][1])
                }

                if(col == 2){

                    resultMap[row][2] = resultMap[row][1] + map[row][2] // 좌측에서 오는 거
                    resultMap[row][2] = Math.min(resultMap[row][2], resultMap[row-1][1] + map[row][2])
                    resultMap[row][2] = Math.min(resultMap[row][2], resultMap[row-1][2] + map[row][2])
                }

            }
        }

        //bw.appendLine(resultMap.contentDeepToString())
        bw.appendLine("${case}. ${resultMap[N-1][1]}")

        case++

    }

    bw.flush()
    bw.close()
}