[프로그래머스/C언어] 완전 범죄, DP로 풀이

2025 프로그래머스 코드 챌린지 2차 예선에 출제되었던 문제인 '완전 범죄'를 동적계획법(DP, Dynamic Programming)을 이용해서 풀어보았다. 

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

프로그래머스

 

 오랜만에 DP 문제를 풀다 보니 조금 헤매기도 했는데, 과거에 풀었던 백준 문제와 유사했기 때문에 점화식을 약간 참고해서 풀이하니 금방 해결할 수 있었다. 참고했던 백준 문제는 아래와 같다.

https://programming-diary-ina.tistory.com/37

[백준 12865번/C언어] 평범한 배낭, 동적계획법으로 풀이 (KnapSack Problem)

 

 

 

처음부터 get_value()와 같은 재귀 함수를 사용할 생각을 했지만, 이내 시간초과 문제에 부딪히게 되었다. 재귀에서 시간초과 문제가 발생하면 보통 DP로 해결했던 기억이 있어, 바로 점화식을 어떻게 세워야 할지부터 고민했던 것 같다. 이 문제에서는 b가 훔칠 물건을 선택할 때, a의 흔적 개수가 큰 물건을 선택해야, 결괏값으로 a가 훔칠 물건들의 흔적 개수가 작아질 수 있다. 그래서 b가 적발되지 않는 limit인 m보다 작은 상태를 유지하면서도, b가 훔칠 물건들의 a의 흔적개수의 총합을 최대화하는 것이 관건이다. 따라서 나는 b가 훔칠 물건들을 선택하는 알고리즘을 짤 때, 해당 물건을 a가 훔쳤을 때의 흔적 개수를 value로, 그리고 b가 훔쳤을 때의 흔적 개수를 cost로 취급하여, cost가 m 이하여야 할 때 낼 수 있는 최대 value를 구한다고 생각하고 접근했다.

그렇게 되면 아래와 같은 점화식을 구할 수 있다. 

F(idx, m) = Max(F(idx-1, m - cost[idx]) + value[idx], F(idx-1, cost[idx-1]))

 b가 훔칠 물건을 선택하는 알고리즘은, idx번째 물건을 탐색하고 있을 때, idx-1번째 물건에 현재의 limitation에서 현재의 cost를 뺀 값을  적용시켜 얻을 수 있는 a의 흔적개수의 최대값과 idx-1번째 물건에 현재의 limitation(m)을 적용시켜 얻을 수 있는 a의 흔적갯수의 최대값 중 더 큰 값에 해당하는 값을 고르는 것이다. 즉, 앞선 경우는 idx번째 물건을 b가 훔치는 경우이고, 두번째 경우는 idx번째 물건을 훔치지 않는 경우이다. F값은 결과적으로 b가 훔친 물건들의 a의 흔적갯수의 최대값이 된다. 

 

이 점화식을 바탕으로 b가 훔친 물건들의 a의 흔적개수의 최대값을 구해주고, 이를 a의 흔적갯수의 총합에서 빼주게 되면, 우리가 원하는 a가 훔친 물건들의 흔적갯수의 최소값이 나온다. 만약 이 값이 a가 훔칠 수 있는 흔적갯수의 최댓값인 n보다 크거나 같으면 문제에서 제시한 대로 -1을 리턴하면 된다. 

#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>

int dp[41][121];

// a의 흔적 갯수를 value, b의 흔적 갯수를 cost로 취급
// a 흔적 갯수를 최대화하여 b가 훔칠 갯수를 선정함
int get_value(int cur, int max, int*** info) {
    if (dp[cur][max] > 0) return dp[cur][max];
    if (cur == 0) {
        if (max <= (*info)[cur][1]) dp[cur][max] = 0;
        else dp[cur][max] = (*info)[cur][0];
        return dp[cur][max];
    }
    
    int pre_val = get_value(cur-1, max, info);
    if (max <= (*info)[cur][1]) dp[cur][max] = pre_val;
    else {
        int cur_val = get_value(cur-1, max-(*info)[cur][1], info) + (*info)[cur][0];
        dp[cur][max] = (pre_val > cur_val) ? pre_val : cur_val;
    }
    return dp[cur][max];
}

// F(idx, m) = Max(F(idx-1, m - cost[idx]) + value[idx], F(idx-1, cost[idx-1]))
int solution(int** info, size_t info_rows, size_t info_cols, int n, int m) {
    int max_a = get_value(info_rows-1, m, &info);
    int tot_a = 0;
    int pre = 0;
    for (int i = 0; i < info_rows; i++) 
        tot_a += info[i][0];
    if (tot_a - max_a >= n) return -1;
    else return tot_a - max_a;
}