[구름톤 챌린지] 통증 (2) (C++)

문제

통증 N과 해당 값 만큼 통증 수치를 감소시켜주는 아이템 A, B가 주어진다.

통증 수치를 0으로 줄이기 위한 아이템의 최소 사용 개수를 출력하기.

단, 통증 수치가 0보다 작아지는 아이템을 사용할 수 없다.

통증 수치를 0으로 만들 수 없는 경우 -1을 출력한다.

생각할 것

처음에는 그리디로 문제를 해결하려 했다.

하지만 예외 상황이 발생했다.

입력

10000
4 13

의 경우 그리디로 해결하면 모든 경우를 확인하지 않았기에 -1의 결과가 나오게 된다.

 

따라서 이 문제는 dp로 해결해야 한다.

1. 먼저 DP배열의 크기를 총 통증 크기 + 1로 만들고, 최대값으로 초기화 한다.
   1. 각 인덱스가 통증의 크기가 되고, 배열의 값은 사용할 수 있는 최소 약의 개수이다.
2. 그리고 1부터 N 까지 모든 경우를 탐색한다.
   1. (i - 통증 감소 수치)가 0보다 큰 경우 해당 약을 사용할 수 있다는 것을 의미한다.
   2. 따라서 현재 dp값과 이전 인덱스에 약 하나를 더한 값을 비교해서 최소값을 설정한다.
3. O(N)의 탐색이 끝난 뒤, dp[N]의 값이 처음 설정한 최대값과 동일하다면 불가능 한 경우이므로 -1을 출력하고, 그렇지 않다면 해당 값을 출력한다.

코드

#include <iostream>
#include <vector>

using namespace std;

int main() {
    int N, A, B;
    cin >> N >> A >> B;
    vector<int> dp(N + 1, 1e9);
    dp[0] = 0;
    for (int i = 1; i <= N; i++) {
        if (0 <= i - A) dp[i] = min(dp[i], dp[i - A] + 1);
        if (0 <= i - B) dp[i] = min(dp[i], dp[i - B] + 1);
    }

    if (dp[N] == 1e9) cout << -1;
    else cout << dp[N];

    return 0;
}