프로그래머스 - 완전범죄

문제 링크 ▶︎ 완전범죄

문제 파악

주어진 info 배열의 인덱스마다 A가 훔치는게 적합할지, B가 훔치는게 적합할지를 경우의 수를 따지면 된다. 그러면 모든 경우의 수가 2^40이 되는데 대략 10^12이므로 완전탐색으로는 풀 수 없다. 그래서 방문을 체크하면서 가지치기하는 백트래킹으로 풀면 된다.

접근 방법

1. 백트래킹 함수에 info 배열과 현재 재귀함수의 인덱스, 그리고 a,b 각각의 현재 흔적의 누적 갯수, 그리고 한계 흔적인 n,m과 방문을 처리하기 위한 Set을 받는다.

2. 탈출 조건으로는 해당 재귀함수에서 index가 info의 길이와 같아졌다면 끝까지 도달한 것이기 때문에 a의 값으로 answer을 최신화해준다.

3. 코드 내부에서는 현재 a와 b의 흔적의 누적 갯수를 이용해서 중복이 불가능한 방문처리 로직을 짜는데, Set에 넣을 것이기 때문에 스트링으로 넣어준다. 만약 해당 인덱스에서 해당 흔적의 누적 갯수를 이미 방문한 상황이라면 이후 처리를 했을 것이기 때문에 또 연산할 필요없이 리턴하면 된다.

4. 그리고 다음 index로 넘기기위해서 a가 훔치는 경우 한번, b가 훔치는 경우한번으로 넘겨주면 된다.

코드 구현

import java.util.*;
class Solution {
    public int answer;
    public boolean flag;
    public int solution(int[][] info, int n, int m) {
        answer = Integer.MAX_VALUE;
        flag = false;
        Set<String> visited = new HashSet<>();
        bt(info, 0, 0, 0, n, m, visited);
        if (!flag) {
            answer = -1;
        }
        return answer;
    }
    public void bt(int[][] info, int idx, int a, int b, int n, int m, Set<String> visited) {
        if(idx == info.length) {
            answer = answer > a ? a : answer;
            flag = true;
            return;
        }
        String key = a + "," + b + "," + idx;
        if (visited.contains(key)) {
            return;
        }
        visited.add(key);
        if (info[idx][0] + a >= n && info[idx][1] >= m) {
            return;
        }
        if (info[idx][0] + a < n) {
            bt(info, idx+1, info[idx][0] + a, b, n, m, visited);
        }
        if (info[idx][1] + b < m) {
            bt(info, idx+1, a, info[idx][1] + b, n, m, visited);
        }
        
    }
}

개선 사항

A의 흔적 누적 갯수가 이미 n을 넘은 재귀함수는 바로 리턴해주면 더 시간을 단축시킬 수 있을 것 같다.