[JS] 완전범죄

문제

프로그래머스

 

풀이

이번 문제는 초반에 접근접을 잘 찾은것같다.

첫 풀이에서는 DFS를 이용해 B가 최대로 많은량의 물건을 가져가 A가 최소의 값을 갖도록 했다.

하지만, 방문 여부를 기록하는 과정에서 문제가 있었고, 이전의 코드에서는 시간 초과가 발생했다.

 

그래서 A와 B의 점수?를 DFS 함수에 전달하여 함수 내부에서 Set 자료형에 현재의 인덱스와 각각의 점수를 기록했다.

이는 해당 물건의 인덱스에서 A가 가져간 경우와 B가 가져간 경우를 따로 계산해야 하기 때문이다.

 

코드

function solution(info, n, m) {
  let answer = Infinity;
  // let visited = new Set();
  let vi = Array.from({ length: info.length }, () => Array.from({ length: n }, () => Array.from({ length: m }, () => false)));
  const dfs = (idx, a, b) => {
    if (idx === info.length) {
      answer = Math.min(answer, a);
      return;
    }
    const nA = a + info[idx][0];
    const nB = b + info[idx][1];
    const check = `${idx}, ${a}, ${b}`
        
    // if(visited.has(check)) return;
    // visited.add(check);
    if (vi[idx][a][b]) return;
    vi[idx][a][b] = true;
        
    if (nA < n && nA < answer) {
      dfs(idx + 1, nA, b);
    }
        
    if (nB < m) {
      dfs(idx + 1, a, nB);
    }
    return;
  }
  dfs(0, 0, 0);
    
  return answer === Infinity ? -1 : answer;
}