[프로그래머스] 118668 코딩 테스트 공부 (C/C++)

문제

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

풀이

문제를 처음 읽었을 때, 상태가 2가지(algorithm_power, coding_power)로 가짓수가 많지 않고, 최대값이 150까지 밖에 되지 않아 동적 계획법(DP)으로 접근해야겠다고 생각했다.

처음에는 아래와 같이 기본적인 동적계획법 풀이로 접근했다.

C++17

#define MAX 150

std::vector<std::vector<size_t>> dp(MAX + 1, std::vector<size_t>(MAX + 1, 2 * MAX));

// 생략된 부분

return dp[max_alp_req][max_cop_req];

그러나 채점 결과 일부 테스트 케이스에서 틀렸다는 것을 확인하고 문제를 다시 읽어보니, 최대값 150 이상의 값에서도 더 작은 값이 나올 수 있다는 것을 놓치고 있었다. 이후 아래와 같이 최대 범위를 $150(최대값) + 30(최대 증가량) = 180$ 으로 늘려 접근했다.

C++17

#define MAX 180

std::vector<std::vector<size_t>> dp(MAX + 1, std::vector<size_t>(MAX + 1, 2 * MAX));

// 생략된 부분

size_t answer = 0;

for (size_t i = max_alp_req; i <= MAX; i++) {
	for (size_t j = max_cop_req; j <= MAX; j++) {
		answer = std::min(answer, dp[i][j]);
	}
}

return answer;

그래도 한두 가지 케이스에서 틀려 다시 깊이 고민했다. 이전 시도에서 범위를 최대 $150 + 30 = 180$ 으로 잡았던 이유는, 최대 증가량이 30이라 최대 크기에서 아무리 벗어나 봤자 30 정도만 벗어날 수 있다는 생각에서였다.

하지만, 더 생각해보니 증가량이 (30, 2)이고 cost가 1인 문제가 있을 때, 최소 비용으로 접근할 수 있는 최대 좌표는 (30 * 75, 2 * 75)로 최대 범위는 $30 * 75 = 2250$ 까지 증가할 수 있음을 깨달았다. (정확하게 계산한 수치는 아니다. 다만, 이런 느낌으로 최대값이 훨씬 더 커질 수 있다는 것을 깨달았다.) 말이 좀 어려운데, 한 쪽 증가량이 1보다 크면서 다른 쪽 증가량 보다 극단적으로 작고, power를 올리기 위해 풀 수 있는 다른 문제가 딱히 없을 때 이런 케이스가 발생할 수 있다. 예를 들어, problems = [[0, 0, 30, 2, 1]], problems = [[0, 0, 3, 20, 1]]과 같은 케이스들.

최종적으로 최대값을 벗어나는 값은 클램핑하여 최대값까지만 증가시키도록 코드를 수정했고, 문제를 해결할 수 있었다. 중간에 클램핑 방식을 떠올리긴 했지만, 2번째 방식과 결과가 같을 것이라 생각해 적용하지 않았다. 만약 바로 클램핑을 적용했다면, 이러한 과정을 깊이 이해하지 못한 채 문제를 마무리했을 수도 있다. 다행히 틀리게 되어 문제를 다시 읽고 고민할 수 있었고, 정확하게 문제를 이해할 수 있었다.

소스 코드

C++17

#include <bits/stdc++.h>

int solution(int alp, int cop, std::vector<std::vector<int>> problems) {
    size_t max_alp_req = 0, max_cop_req = 0;

    for (const auto &problem: problems) {
        max_alp_req = std::max(max_alp_req, static_cast<size_t>(problem[0]));
        max_cop_req = std::max(max_cop_req, static_cast<size_t>(problem[1]));
    }

    std::vector<std::vector<size_t>> dp(max_alp_req + 2, std::vector<size_t>(max_cop_req + 2, 300));

    alp = std::min(alp, static_cast<int>(max_alp_req));
    cop = std::min(cop, static_cast<int>(max_cop_req));

    dp[alp][cop] = 0;

    for (size_t i = alp; i <= max_alp_req; i++) {
        for (size_t j = cop; j <= max_cop_req; j++) {
            dp[i + 1][j] = std::min(dp[i + 1][j], dp[i][j] + 1);
            dp[i][j + 1] = std::min(dp[i][j + 1], dp[i][j] + 1);
            for (const auto &problem: problems) {
                if (i < problem[0] || j < problem[1]) {
                    continue;
                }

                const size_t next_i = std::min(i + problem[2], max_alp_req);
                const size_t next_j = std::min(j + problem[3], max_cop_req);

                dp[next_i][next_j] = std::min(dp[next_i][next_j], dp[i][j] + problem[4]);
            }
        }
    }

    return dp[max_alp_req][max_cop_req];
}

[프로그래머스] 118668 코딩 테스트 공부 (C/C++)

문제

풀이

소스 코드

Share this post