[Swift] 프로그래머스_양궁대회

문제

 

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

프로그래머스

 

 

풀이

 

이 문제를 풀어보면서 정말 많이 모자라다고 느꼈음. 모든 경우의 수를 구할 때 점수를 얻었을 때와 못얻었을때로 나눠서 생각했어야했는데 처음엔 못했었음.

 

아무튼 이 문제는 dfs를 이용해서 해결했는데, 라이언이 이길 수 있는 모든 경우의 수를 구한 뒤에 가장 큰 점수차를 갖는 것 중에서 낮은 점수를 맞춘 화살 수가 더 많은 것을 리턴해주었음.

 

우선 처음에 apeach라는 변수에 라이언이 화살을 쏘지 않았을 때의 어피치 점수를 넣어주었음.

 

이후에 dfs를 이용하여 라이언이 이길 수 있는 모든 경우의 수를 구해주었음. idx값을 1씩 증가시켜가면서 해당 점수를 얻었을 때와 못얻었을때의 두 가지 경우 모두 dfs를 다시 호출하여 경우의 수를 구함. n개의 화살을 전부 다 쏴야하므로 마지막 인덱스에서는 남은 화살을 전부 넣어주었음.

근데 점수를 얻는 경우에는 score값을 바꿔줘야함. 만약 어피치가 얻지 못한 점수였으면 그냥 해당 점수만큼 한 번만 빼주면 점수차가 줄어듦. 반대로 어피치가 얻은 점수였다면 어피치는 점수를 잃고 라이언은 점수를 얻기 때문에 점수차인 score값에서 해당 점수를 두 번 빼줘야함.

 

이렇게해서 모든 경우를 구한 뒤엔 maxScore를 갖는 경우 중에서, 낮은 점수에 화살을 가장 많이 맞춘 경우를 반환해줬음.

import Foundation

func solution(_ n:Int, _ info:[Int]) -> [Int] {

    var result: [[[Int]]] = [] // [[[과녁],[점수]]]
    var apeach = 0
    for i in 0..<10 {
        if info[i] != 0 {
            apeach -= 10 - i
        }
    }
    var maxScore = 0
    func dfs(_ arr: [Int], _ count: Int, _ score: Int, _ idx: Int) {
        var temp = arr
        if count == n || idx == 10 {
            temp[10] = n - count
            if score > 0 {
                result.append([temp,[score]])
                maxScore = max(maxScore, score)
            }
            return
        }
        //맞췄을 때
        if n - count >= info[idx] + 1 {
            temp[idx] = info[idx] + 1
            if info[idx] == 0 {
                dfs(temp, count + info[idx] + 1, score + 10 - idx, idx + 1)
            } else {
                dfs(temp, count + info[idx] + 1, score + 20 - idx * 2, idx + 1)
            }
        }
        //못
        temp[idx] = 0
        dfs(temp,count, score, idx + 1)
    }
    dfs([0,0,0,0,0,0,0,0,0,0,0],0,apeach,0)
    result = result.filter { $0[1][0] == maxScore }
    if result.count == 0 {
        return [-1]
    }
    for i in stride(from: 10, through: 0, by: -1) {
        var temp = [0,0] //idx,화살수
        for j in 0..<result.count {
            if result[j][0][i] != 0 && temp[1] < result[j][0][i] {
                temp[0] = j
                temp[1] = result[j][0][i]
            }
        }
        if temp != [0,0] {
            return result[temp[0]][0]
        }
    }
    return result[0][0]
}

 

 

_____________________________________________________________________________________________________

 

어려워