Leetcode - 1753. Maximum Score From Removing Stones

문제

3개의 돌더미가 주어지고, 매 게임마다 두개의 돌더미에서 돌을 하나씩 뺄때, 두개이상의 돌더미가 0개가 되는 최대 게임 횟수.

https://leetcode.com/problems/maximum-score-from-removing-stones/

Input: a = 2, b = 4, c = 6
Output: 6
Explanation: The starting state is (2, 4, 6). One optimal set of moves is:
- Take from 1st and 3rd piles, state is now (1, 4, 5)
- Take from 1st and 3rd piles, state is now (0, 4, 4)
- Take from 2nd and 3rd piles, state is now (0, 3, 3)
- Take from 2nd and 3rd piles, state is now (0, 2, 2)
- Take from 2nd and 3rd piles, state is now (0, 1, 1)
- Take from 2nd and 3rd piles, state is now (0, 0, 0)
There are fewer than two non-empty piles, so the game ends. Total: 6 points.

해결 O(N)

매 게임마다 가장 큰값에서 -1 가장 작은값에서 -1 을 하고 0개가 되는 돌이 2개 이상이 되면 종료. 그리고 게임 횟수 출력. 매 게임마다 그렇게 수행하는게 최적의 선택임이 보장되므로 그리디한 해결방법임.

qsort를 이용해 매번 배열을 정렬하고 max값은 arr[2]에서, min값은 0이아닌 가장 앞 idx에서 얻음. 시간복잡도는 돌의 갯수정도의 Linear time.

Runtime: 188 ms, faster than 100.00% 
Memory Usage: 5.4 MB, less than 100.00% 

int cmp(const void *a, const void *b)
{
    return *(int *)a - *(int *)b;
}

int zero_cnt(int arr[])
{
    int cnt = 0;
    for (int i = 0; i < 3; i++)
        if (arr[i] == 0)
            cnt++;
    return cnt;
}

int get_min(int arr[])
{
    for (int i = 0; i < 3; i++)
        if (arr[i] != 0)
            return i;
    return 0;
}

int maximumScore(int a, int b, int c){
    int arr[3] = {a, b, c};
    int cnt = 0;
    while (zero_cnt(arr) < 2) {
        qsort(arr, 3, sizeof(int), cmp);
        arr[get_min(arr)]--;
        if (arr[2] > 0) arr[2]--;
        cnt++;
    }
    return cnt;
}