백준 28422 XOR 카드 게임 / python

문제 : 28422

풀이 point

2개 혹은 3개를 가져갈 수 있는 상태에서 가장 최대의 값을 찾아야한다. DP로 구할 수 있다.

점화식을 세워보자. 우선 카드가 1개만 있을 때는 당연히 이 카드 숫자의 1의 개수가 최대다. 2개일 때는 2개를 뽑았을 때 최대가 된다. 3개일때도 3개가 최대가 된다. 4개일때는 어떨까?
4개일때는 3개가 성립되지 않는다.(최소 카드를 2개 이상 뽑아야하기 때문에 1 + 3 구조가 안됨)

5개 일때부터 패턴이 시작된다. 경우의 수가 두가지로 나뉜다.

1. i-1, i XOR(2개 뽑기)
2. i-2, i-1, i XOR(3개 뽑기)

이때 우리는 점수의 최대를 알아야하기 때문에 첫번째 경우일 때는 dp[i-2] 값을 더해주어야 하고 두번째 경우일 때는 dp[i-3] 값을 더해주어야 한다.

ex) 2 1 3 8 4
dp[1, 2, 0, 5, 6]
6의 경우는 두 경우의 수를 보았을 때
1. dp[3] + 8^4
2. dp[2] + 3^8^4
이 중 2번째 경우의 값이 더 크므로 선택이 되었다.

풀이 코드

N = int(input())

nums = [0] + list(map(int, input().split()))

dp = [0]*(N+1)

if N == 1:
  print(0)
  exit()
dp[2] = (nums[1] ^ nums[2]).bit_count()

if N == 2:
  print(dp[2])
  exit()

dp[3] = (nums[1] ^ nums[2] ^ nums[3]).bit_count()
if N == 3:
  print(dp[3])
  exit()

dp[4] = dp[2] + (nums[3] ^ nums[4]).bit_count()
if N == 4:
  print(dp[4])
  exit()

for i in range(5, N+1):
  dp[i] = max(dp[i-2] + (nums[i] ^ nums[i-1]).bit_count(),
              dp[i-3] + (nums[i] ^ nums[i-1] ^ nums[i-2]).bit_count())

print(0 if N == 1 else dp[N])