완전 범죄

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

프로그래머스

info의 각 행마다 이전 행에서 현재 행에 a(info[0]) OR b(info[1])을 선택했을 때 최종 행에서 a가 가장 작은 값을 출력하면 되는 문제이다.

만약 이를 완전 탐색을 사용하여 코드르 짤 경우 각 행마다 두가지의 경우의 수가 생겨서 총 2 ^ (info.length)의 경우가 생긴다. info의 최대 길이는40이므로 2^40은 무조건 시간 초과가 발생하여 최적화 된 탐색이 필요하다. 

이 경우 생각할 수 있는 것은 그리디 또는 dp인데 각 행마다 적힌 수들은 다르므로 현재의 값이 항상 최선임을 보장 해야 하는 그리디의 성질에는 맞지 않기에 dp를 사용해야 한다. 

현재 행에서 최소의 A흔적은 ( 이전의 A흔적 최소 값 + curA ) , ( 이전의 A흔적 최소 값 + curB )중 작은 값이 된다. 

이것을 위해 각 행 별로 A의 최솟값을 기록할 필요가 있어다. 이때 B의 흔적까지 고려해야 하므로 

info를 탐색하는 각 행에서 B의 흔적 값을 사용할 경우 나올 수 있는 A의 흔적을 항상 최소로 기록하는 점화식을 만들면 됐다. 

이를 dp화 시키면 아래 코드가 된다.

const INF = n;
const size = info.length;

// dp[i][j] = i번째 물건까지 처리하면서, B도둑의 흔적이 j개일 때, A도둑의 최소 흔적 개수를 기록하기
const dp = Array.from({ length: size + 1 }, () => Array(m).fill(INF));

// 초기 상태: 아무 물건도 안 훔쳤을 때 두 도둑 모두 흔적 0개
dp[0][0] = 0;

A의 흔적은 항상 n보다 작아야 하므로 INF는 n으로 둠.

이제 info의 행을 탐색 해가면서 B의 흔적값을 0부터 m-1까지 탐색해가면서 

현재 행에서 a를 선택했다면 이전 행의 같은B의 흔적값을 사용했을 경우에 기록해뒀던 최소한의 A 흔적값에 지금의 A흔적값을 더하고 이를 현재 행렬의 값과 비교하여 최소를 기록하면 됨.

만약 현재 행에서 b를 선택했다면, b의 총 흔적이 m 미만 인 것을 감안하여 이전 행렬의 b 흔적에 현재 b를 더했을 때의 기록 된 최소의 A흔적값을 기록한다.

for (let i = 1; i <= size; i++) {
    const [a, b] = info[i - 1];

    for (let j = 0; j < m; j++) {
        // A의 흔적 a 증가, B의 흔적은 그대로 유지 (j → j)
        dp[i][j] = Math.min(dp[i][j], dp[i - 1][j] + a);

        // B의 흔적 b 증가 (j → j+b), A의 흔적은 그대로 유지
        if (j + b < m) {
            // B도둑이 경찰에 안 잡히는 경우만 가능 (흔적 개수 < m)
            dp[i][j + b] = Math.min(dp[i][j + b], dp[i - 1][j]);
        }
    }
}

이제 dp마지막 행에서 가장 최소의 a흔적값을 찾고 이것이 만약 n이상이라면 -1을 출력하면 됨.

let min = n;
for (let j = 0; j < m; j++) {
    min = Math.min(min, dp[size][j]);
}

// A도둑의 흔적이 n 미만이면 답 반환, 아니면 -1 (둘 다 안 잡히는 방법이 없음)
return min >= n ? -1 : min;

function solution(info, n, m) {
    const INF = n + 1;
    const size = info.length;

    // dp[i][j] = i번째 물건까지 처리하면서, B도둑의 흔적이 j개일 때, A도둑의 최소 흔적 개수를 기록하기
    const dp = Array.from({ length: size + 1 }, () => Array(m).fill(INF));

    // 초기 상태: 아무 물건도 안 훔쳤을 때 두 도둑 모두 흔적 0개
    dp[0][0] = 0;

    // 각 물건에 대해 A 또는 B 중 누가 훔칠지 결정
    for (let i = 1; i <= size; i++) {
        const [a, b] = info[i - 1];

        for (let j = 0; j < m; j++) {
            // A의 흔적 a 증가, B의 흔적은 그대로 유지 (j → j)
            dp[i][j] = Math.min(dp[i][j], dp[i - 1][j] + a);

            // B의 흔적 b 증가 (j → j+b), A의 흔적은 그대로 유지
            if (j + b < m) {
                // B도둑이 경찰에 안 잡히는 경우만 가능 (흔적 개수 < m)
                dp[i][j + b] = Math.min(dp[i][j + b], dp[i - 1][j]);
            }
        }
    }

    // 모든 물건을 훔친 후, B의 흔적이 어떤 값이든 상관없이 A의 최소 흔적 찾기
    let min = n;
    for (let j = 0; j < m; j++) {
        min = Math.min(min, dp[size][j]);
    }

    return min >= n ? -1 : min;
}