[알고리즘][KOTLIN] 양궁대회

https://school.programmers.co.kr/learn/courses/30/lessons/92342

프로그래머스

문제 풀이

1. 쏴야할 화살의 개수를 저장하는 max 를 선언한다.

2. 라이언이 쏜 화살 정보를 저장하는 result List 를 선언한다.

3. dfs 를 이용하여 어피치 화살 정보를 완전탐색하여 라이언이 이기는 경우는 탐색 한다.

    3-1. 라이언의 남은 화살 개수(arrow)가 0이 되면 dfs 탈출 조건으로 result list 에 결과를 업데이트 한다.

    3-2. index i 가 10일 경우 마지막 기회이므로 라이언은 이기던 지던 남은 화살은 다 쏜다.

    3-3. 라이언이 쏠 화살 >= 어피치의 화살 정보 + 1 조건에 해당될 경우 라이언 화살을 소모하고 남은 화살 개수를 이용하여 dfs 를 수행한다.

    3-4. 라이언의 남은 화살 개수가 0이 될때까지 3 번과정을 반복한다.

4. result list 를 업데이트 할 때 현재 저장된 max 값과 라이언과 어피치 점수 차이의 값이 같을 경우 조건에 따라 ryonInfo 와 result 에 저장된 정보를 비교하여 가장 낮은 점수를 많이 쏜 정보로 업데이트 한다.

코드

class Solution {
    var max = 0
    var result = mutableListOf<Int>()
    
    fun solution(n: Int, info: IntArray): IntArray {
        val ryonInfo = IntArray(11) { 0 }
        dfs(n, info, ryonInfo, -1, n)
        return if (max > 0) result.toIntArray() else intArrayOf(-1)
    }
    
    // arrow : 라이언 화살 개수
    // appchInfo : 어피치 화살 쏜 정보
    // ryonInfo : 라이언 화살 쏜 정보
    // idx : 검색 index
    // maxArrow : 총 화살 개수
    private fun dfs(arrow: Int, apeechInfo: IntArray, ryonInfo: IntArray, idx: Int, maxArrow: Int) {
        // 라이언 화살을 다 쐈음...
        if (arrow == 0) {
            var ryonTotal = 0
            var apeechTotal = 0
            
            /*println("Apeech>>>>>")
            apeechInfo.forEach { apeech ->
                print("$apeech ")
            }
            println()
            
            println("Ryon>>>>>")
            ryonInfo.forEach { ryon ->
                print("$ryon ")
            }
            println()*/
            
            
            // 라이언/어피치 점수 계산
            for (i in 0..10) {
                if (ryonInfo[i] > apeechInfo[i]) ryonTotal += 10 - i
                else {
                    if (apeechInfo[i] > 0) {
                        apeechTotal += 10 - i    
                    }
                }
            }
            
            //println("apeechTotal=$apeechTotal, ryonTotal=$ryonTotal")
            
            if (max < ryonTotal - apeechTotal) {
                result = ryonInfo.toMutableList()
                max = ryonTotal - apeechTotal
            } else if (max > 0 && (max == ryonTotal - apeechTotal)) {
                for (j in 10 downTo 0) {
                    // 가장 낮은 점수를 많이 쏜 리스트를 저장 한다.
                    if (ryonInfo[j] > result[j]) {
                        result = ryonInfo.toMutableList()
                        max = ryonTotal - apeechTotal   
                    } else if (ryonInfo[j] < result[j]) {
                        return
                    }
                }
            }
            
            return
        }
        
        
        for (i in idx + 1..10) {
            val newRyonInfo = IntArray(11) { 0 }
            
            // 입력으로 들어온 ryonInfo 를 깊은 복사 한다.
            for (i in 0..10) newRyonInfo[i] = ryonInfo[i]
            
            //println("currentIdx : $i")
            
            if (i == 10) {
                // i 가 10일 경우 마지막 점수이므로 화살을 다 소모 한다.
                newRyonInfo[i] = arrow
                dfs(0, apeechInfo, newRyonInfo, i, maxArrow)
            } else if (arrow >= apeechInfo[i] + 1) {
                val remainArrow = arrow - (apeechInfo[i] + 1)
                newRyonInfo[i] = apeechInfo[i] + 1
                //println("newRyonInfo[$i] = ${newRyonInfo[i]}, $remainArrow")
                dfs(remainArrow, apeechInfo, newRyonInfo, i, maxArrow)
            }
        }
    }
}