1753. Maximum Score From Removing Stones [Medium]

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

Maximum Score From Removing Stones - LeetCode

 

각각 a,b,c 크기의 돌 더미 3개로 솔리테어 게임(?)을 하는데, 매 턴마다 비어있지 않은 2개의 돌 더미에서 각각 1개씩 빼야한다.

비어있는 더미가 2개가 되면 게임은 종료된다.

결국 최대 진행 가능한 턴 수를 구하는 문제다.

 

요점은 최대한 턴 수를 증가시켜야 하므로 3개의 돌 더미에서 고르게 차감해야 한다.

example

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.

Input: a = 4, b = 4, c = 6 Output: 7 Explanation: The starting state is (4, 4, 6). One optimal set of moves is: - Take from 1st and 2nd piles, state is now (3, 3, 6) - Take from 1st and 3rd piles, state is now (2, 3, 5) - Take from 1st and 3rd piles, state is now (1, 3, 4) - Take from 1st 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: 7 points.

Input: a = 1, b = 8, c = 8 Output: 8 Explanation: One optimal set of moves is to take from the 2nd and 3rd piles for 8 turns until they are empty. After that, there are fewer than two non-empty piles, so the game ends.

 

 

실행 결과

Explanation

array<int, 3> arr; int maximumScore(int a, int b, int c) {     arr[0] = a; arr[1] = b; arr[2] = c;     sort(arr.begin(), arr.end(), greater<int>());     a = arr[0]; b = arr[1]; c = arr[2];     // 2개 이상이 비었을 때 종료니까 중간이 비면 over     if (0 == b) {         return 0;     }     // 제일 작은 것 두개의 차이를 상위 2개에 뺀다 (최소 1개 이상)      // 그래야 3개의 돌더미의 숫자가 서로 비슷하게 되어 오랜 게임이 가능하기 때문이다.     int cnt = max(1, b - c);     return cnt + maximumScore(         a - cnt,         b - cnt,         c); }

a=2, b=4, c=6일 때 1회차: a=6, b=4, c=2 -> cnt=2, a=4, b=2, c=2 2회차: a=4, b=2, c=2 -> cnt=1, a=3, b=1, c=2 3회차: a=3, b=2, c=1 -> cnt=1, a=2, b=1, c=1 4회차: a=2, b=1, c=1 -> cnt=1, a=1, b=0, c=1 5회차: a=1, b=1, c=0 -> cnt=1, a=0, b=0, c=0 cnt=6 -end- a=4, b=4, c=6 1회차: a=6, b=4, c=4 -> cnt=1, a=5, b=3, c=4 2회차: a=5, b=4, c=3 -> cnt=1, a=4, b=3, c=3 3회차: a=4, b=3, c=3 -> cnt=1, a=3, b=2, c=3 4회차: a=3, b=3, c=2 -> cnt=1, a=2, b=2, c=2 5회차: a=2, b=2, c=2 -> cnt=1, a=1, b=1, c=2 6회차: a=2, b=1, c=1 -> cnt=1, a=1, b=0, c=1 7회차: a=1, b=1, c=0 -> cnt=1, a=0, b=0, c=0 cnt=7 -end- a=1, b=8, c=8 1회차: a=8, b=8, c=1 -> cnt=7, a=1, b=1, c=1 2회차: a=1, b=1, c=1 -> cnt=1, a=0, b=0, c=1 cnt=8 -end-

나는 a, b, c의 정렬을 std::sort 함수를 사용해서 작업했지만, 다른 사람의 풀이를 보니 if문을 활용한 재귀함수로 구현한 사람도 있었다..