[프로그래머스] 광물 캐기 문제풀이 JS

DFS를 이용해 문제를 풀었다.

tiredList에 각 곡괭이 별로 광물을 캤을때 피로도 정도를 저장했다.

max는 몇개의 광물을 캘 수 있는지로,

picks로 주어진 곡괭이는 5개의 광물을 캘 수 있으므로

곡괭이가 소진되어 광물을 모두 못 캘 때는 곡괭이로 캘 수 있는 최대의 광물 개수가 max고,

그 외의 경우엔 모든 광물의 개수가 max이다.

 

DFS(0,0)을 실행한다.

level이 max에 도달했을 때 피로도의 누적이 answer값보다 작으면 answer를 해당 sum으로 업데이트 한다.

 

0~2의 picks를 확인해서 해당 picks의 곡괭이가 남아있다면 (picks[i] >0)

5개의 광물을 캐고, 이 과정에서 캔 광물의 수가 max에 도달 했다면 answer를 업데이트하고 반복문을 종료한다.

5개의 광물을 캐면서 광물 별로 쌓이는 피로도의 누적을 업데이트한다.

level에 5를 더했을때, max보다 작거나 같다면 DFS를 level은 5증가, sum에는 현재 쌓인 피로도를 업데이트해서 실행한다.

 

모든 과정을 반복했을 때는 answer에 누적 피로도가 가장 낮은값이 저장되어, 원하는 값을 구할 수 있다.

function solution(picks, minerals) {
  let answer = 1000
  const tiredList = [
    [1, 1, 1],
    [5, 1, 1],
    [25, 5, 1],
  ]
  const max = Math.min((picks[0] + picks[1] + picks[2]) * 5, minerals.length)
  const DFS = (level, sum) => {
    if (level === max) {
      answer = Math.min(sum, answer)
    } else {
      for (let i = 0; i < 3; i++) {
        if (picks[i] > 0) {
          picks[i]--
          let tired = 0
          for (let j = 0; j < 5; j++) {
            if (level + j === max) {
              answer = Math.min(tired + sum, answer)
              break
            }
            if (minerals[level + j] === 'diamond') tired += tiredList[i][0]
            else if (minerals[level + j] === 'iron') tired += tiredList[i][1]
            else tired += tiredList[i][2]
          }
          if (level + 5 <= max) DFS(level + 5, sum + tired)
          picks[i]++
        }
      }
    }
  }
  DFS(0, 0)
  return answer
}

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

프로그래머스