1664. Ways to Make a Fair Array

1664. Ways to Make a Fair Array

https://leetcode.com/problems/ways-to-make-a-fair-array/

문제

풀이

nums = [2, 1, 6, 4]일 때
인덱스 별로 홀수, 짝수일 때 총합을 저장해 두자.
i = 0일 때 (0, 홀수) = 0, (0, 짝수) = 2
i = 1일 때 (1, 홀수) = 1, (1, 짝수) = 2
i = 2일 때 (2, 홀수) = 1, (2, 짝수) = 8
i = 3일 때 (3, 홀수) = 5, (2, 짝수) = 8
만약 i = 1을 제거해 보자
i = 0까지는 그대로 가져오면 될 것이고
i = 2,3은 홀수, 짝수가 바뀐 값을 가지고 오면 될 것이다.
즉 짝수 = 2 + (5-1) = 6, 홀수 0 + (8-2) = 6이 된다.

dp에는 인덱스별로 홀수, 짝수 총합이 저장된다. 만약 dp[(3, True)]이면 인덱스3 짝수 총합이고 dp[(3, False)]면 인덱스3 홀수 총합이다.
그 후 인덱스 기준으로 왼쪽은 left, 오른쪽은 right라 생각하고 left의 짝수 총합은 left_even, left 홀수 총합은 left_odd, right의 짝수 총합은 right_even, 홀수의 총합은 right_odd라 둔다.

결과