1049. Last Stone Weight II

1049. Last Stone Weight II

https://leetcode.com/problems/last-stone-weight-ii/

문제

풀이

Example 1 기준으로 생각해보면
stones = [2, 7, 4, 1, 8, 1]이고 S1 = [2, 7, 4] S2 = [1, 8, 1]이라고 하자
1. S1에서 2, S2에서 1을 smash시키면
S1 = [1, 7, 4], S2 = [8, 1]이 된다.
2. S1에서 1, S2에서 1을 smash시키면
S1 = [7, 4] S2 = [8]이 된다.
3. S1에서 7, S2에서 8을 smash시키면
S1 = [4], S2 = [1]이 된다.
4. S1에서 4, S2에서 1을 smash시키면
S1= [3], S2 = []가 된다. 즉 차이가 3이된다.

즉 크게 S1, S2로 나누고 S1 - S2의 차이가 가장 작은 것을 구하는 문제와 같다.
키포인트는 sum(stones) = 23이고 23 // 2값인 11을 S1에서 만들 수 있는지 확인하는 것이다. 만약 S1이 11이라면 S2는 당연히 23 - 11 = 12이고 차이는 abs(-1) = 1이 될 것이다. 이것을 코드화하면 다음과 같다.

결과