[Hackerrank][C++] Equal

문제 링크: https://www.hackerrank.com/challenges/equal

 

해커랭크에 있는 DP 분류 문제 중 맨 위에 있길래 풀어봤습니다.

DP라고 써있지만 딱히 DP로 풀지는 않아도 되는? 그런 문제입니다만 문제 분류가 DP로 되어 있으니 그렇게 풀어봤습니다.

 

일단 i번째 사람 빼고 모두에게 초콜릿을 나눠주는거를 역으로 생각하면 i번째 사람의 초콜릿 개수를 뺀다고 생각할 수 있습니다.

여기서 점화식을 하나 생각해낼 수 있습니다.

\begin{align}
dp[0] &= 0 \\
dp[n] &= min(dp[n-1], dp[n-2], dp[n-5]) + 1
\end{align}

dp[i] = i개의 초콜릿을 0개로 만드는 데 걸리는 최소 연산 횟수라고 해봅시다. 이때 1회 연산시 초콜릿을 1개, 2개, 또는 5개를 뺀다고 생각해보면 위 점화식을 도출할 수 있습니다.

 

그 다음, 배열에서 최솟값을 찾아 전부 빼줍니다. 예를 들어 예제에 있는 {2, 2, 3, 7}의 경우 최솟값이 2이므로 각 원소에 최솟값을 다 빼면 {0, 0, 1, 5}가 됩니다.

 

이제 문제를 풀 수 있습니다. 배열이 {2, 2, 3, 7}인 경우 {0, 0, 1, 5}가 되고 이 때 dp[0]+dp[0]+dp[1]+dp[5]=0+0+1+1=2로 예제 정답과 같아집니다.

여기서 끝이냐? 아닙니다. 배열 각 원소에 1, 2를 더해본 뒤 그때의 dp값의 합도 구해봐야 합니다. 왜냐면 그렇게 했을 때 최소값이 변하는 반례(ex. {1, 4, 4})가 있기 때문입니다.

 

코드로 보는게 더 이해가 빠를 것 같습니다.

#pragma GCC optimize ("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,avx,avx2")

#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
using namespace std;


const int INF = 987654321;

int dp[1005];

int solve(int n) {
    int& ret = dp[n];
    if (ret != -1) return ret;

    ret = solve(n-1)+1;
    if (n - 2 >= 0) ret = min(ret, solve(n-2) + 1);
    if (n - 5 >= 0) ret = min(ret, solve(n-5) + 1);

    return ret;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);


    memset(dp, -1, sizeof(dp));
    dp[0] = 0;

    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        vector<int> arr(n);
        for (auto& c : arr)
            cin >> c;

        int min_val = *min_element(arr.begin(), arr.end());

        for (auto& c : arr)
            c -= min_val;

        int cnt0 = 0, cnt1 = 0, cnt2 = 0;
        for (auto& c : arr) {
            cnt0 += solve(c);
            cnt1 += solve(c + 1);
            cnt2 += solve(c + 2);
        }
        cout << min({cnt0, cnt1, cnt2}) << '\n';
    }
    
    return 0;
}