[Python] 28422번 XOR 카드 게임

https://www.acmicpc.net/problem/28422

---

 

24/04/10

 

 

간단한 DP문제다. 이 문제를 통해 파이썬의 bit_count라는 좋은 내장함수를 알 수 있었다.

---

 

문제 접근 방식:

 

 

문제를 요약하면, 쌓인 카드 더미에서 카드를 2장 혹은 3장씩만 가져갈 수 있는데, 카드에 쓰인 모든 숫자를 XOR하고 그 값을 이진수로 변환했을 때 1의 개수만큼 내가 점수를 획득할 수 있다고 한다. 그때, 이 게임에서 얻을 수 있는 최고의 점수를 구하는 것이 문제이다.

 

카드는 2장 혹은 3장 단위로만 가져갈 수 있으므로 마지막에 카드가 1장이 남는 상황이라면 모든 점수가 0이 된다.

 

다음과 같이 DP식을 세우자.

$$DP[i] = i\text{장을 가져갔을 때 얻을수 있는 최고 점수}$$

 

이 식에 따르면, DP[N-1]의 값은 0이 됨은 쉽게 확인할 수 있다.

 

카드를 2장 아니면 3장을 가져갈 수 있으므로 점화식은 다음과 같이 정의된다.

$$DP[i] = \text{max}(DP[i-2] + 2\text{장 가져갔을 때의 점수}, DP[i-3] + 3\text{장 가져갔을 때의 점수})$$

 

우리의 목적은 $DP[N]$을 구하는 것이 목적이다.

 

나는 바텀업으로 구현했는데, 카드가 2장일 때, 3장일 때의 경우를 조금 처리하기가 곤란하여 따로 예외처리를 해주어 빼두었고, 2장만 가져갈 수 있는 경우나, 3장만 가져갈 수 있는 경우일 때를 따로 예외처리 해주어서 점화식을 구현했다.

 

파이썬에서 bit_count이라는 좋은 함수가 있다. 꽤 최근에 추가된 모양인 듯 하다.

아래 공식 도큐먼트를 참고해보자.

https://docs.python.org/3/library/stdtypes.html#int.bit_count

Built-in Types

 

이를 통해 XOR한 값의 비트가 몇 개가 켜져있는지 그냥 확인할 수 있다.

---

아래는 내가 위의 접근 방식과 같이 작성한 파이썬 코드이다. 더보기를 누르면 확인할 수 있다.

# 28442번 XOR 카드 게임
# DP
'''
접근 방법:
카드를 2장 혹은 3장씩 가져감.
가져가는 카드의 번호를 모두 XOR하고, 그 값을 이진수로 변환했을 때 1의 개수만큼
점수를 획득.
마지막에 카드 1장이 남는 상황이라면 모든 점수가 0.
이 게임에서 얻을 수 있는 최고 점수는?
DP[i] = i장을 가져갔을 때 얻을 수 있는 최고 점수.
DP[N-1] = 0
DP[i] = max(DP[i-2]+2장, DP[i-3]+3장)
우리는 DP[N]을 구하는 것이 목적임.
'''
import sys
input = sys.stdin.readline

def solve():
    N = int(input())
    A = list(map(int, input().split()))
    DP = [-1 for _ in range(N+1)]
    if N == 1:
        print(0)
        return
    DP[2] = (A[0]^A[1]).bit_count()
    if N == 2:
        print(DP[2])
        return
    DP[3] = (A[0]^A[1]^A[2]).bit_count()
    if N == 3:
        print(DP[3])
        return
    for i in range(4, N+1):
        two = (A[i-1]^A[i-2]).bit_count()
        three = (A[i-1]^A[i-2]^A[i-3]).bit_count()
        if DP[i-2] == -1:
            DP[i] = DP[i-3]+three
        elif DP[i-3] == -1:
            DP[i] = DP[i-2]+two
        else:
            DP[i] = max(DP[i-2]+two, DP[i-3]+three)
    print(DP[N])
solve()