코테-2025.03.13 ( java )

class Solution {
    int minTrace;
    int n, m; // 경찰에 잡히는 임계치
    int[][] info; // 물건 정보

    public int solution(int[][] info, int n, int m) {
        int answer = -1; // 기본적으로 불가능한 경우 -1 반환
        this.n = n;
        this.m = m;
        this.info = info;
        this.minTrace = Integer.MAX_VALUE;

        // DFS 탐색 시작 (idx=0, 현재 흔적: A=0, B=0)
        dfs(0, 0, 0);

        // 최적의 A 도둑 흔적 값이 갱신된 경우 반환
        if (minTrace != Integer.MAX_VALUE) {
            answer = minTrace;
        }

        return answer;
    }

    // DFS 탐색 (idx: 현재 탐색 중인 물건, sumA: A 도둑의 흔적 합, sumB: B 도둑의 흔적 합)
    private void dfs(int idx, int sumA, int sumB) {
        // A 또는 B 도둑이 경찰에 붙잡히면 종료 (백트래킹)
        if (sumA >= n || sumB >= m) return;

        // 모든 물건을 다 훔쳤다면, 최소 A 흔적 값 업데이트
        if (idx == info.length) {
            minTrace = Math.min(minTrace, sumA);
            return;
        }

        // 1. 현재 물건을 A 도둑이 훔치는 경우
        dfs(idx + 1, sumA + info[idx][0], sumB);

        // 2. 현재 물건을 B 도둑이 훔치는 경우
        dfs(idx + 1, sumA, sumB + info[idx][1]);
    }

    public static void main(String[] args) {
        Solution solution = new Solution();

        int[][] info1 = {{1, 2}, {2, 3}, {2, 1}};
        int result1 = solution.solution(info1, 4, 4);
        System.out.println(result1); // 예상 출력: 2

        int[][] info2 = {{1, 2}, {2, 3}, {2, 1}};
        int result2 = solution.solution(info2, 1, 7);
        System.out.println(result2); // 예상 출력: 0

        int[][] info3 = {{3, 3}, {3, 3}};
        int result3 = solution.solution(info3, 7, 1);
        System.out.println(result3); // 예상 출력: 6

        int[][] info4 = {{3, 3}, {3, 3}};
        int result4 = solution.solution(info4, 6, 1);
        System.out.println(result4); // 예상 출력: -1
    }
}

코딩테스트를 자주 해야할 것 같아요 너무 부족한부분이 많네요
직접 짠건아니고 찾아보면서 만들었어요

dfs를 사용해서 재귀적으로 풀면 테스트할때 시간이 너무오래걸려요
DP를 사용해서 내일 다시 도전