[Python] 백준 23257 비트코인은 신이고 나는 무적이다

문제 링크 : https://www.acmicpc.net/problem/23257

23257번: 비트코인은 신이고 나는 무적이다

1. 접근 방법

처음에는 XOR 연산에 대해 고민했는데, XOR 연산 처리는 비교적 쉽게 방법을 찾았다.

https://stackoverflow.com/questions/52108901/xor-operation-on-three-values

XOR operation on three values

위의 링크에서 A^B^C = (A^B) | (B^C)로 연산 가능하다는 것을 알 수 있었고, 이 식을 응용하여 해결했다. 그리고 조금 더 나가면 A^B^C = (A^B)^C 로 순서대로 연산해도 된다. 처음 방식으로 풀어낸 것이 아래의 풀이 2이고, 두 번째 방법으로 풀어낸 것이 풀이 1이다.

XOR 연산을 알아낸 후에는 배낭문제처럼 해결했다.

 

 

2. 해결 코드

🖥python 코드

import sys
input = sys.stdin.readline
MIIS = lambda: map(int, input().split())

# 풀이 1
n, m = MIIS()
montly_bong = list(abs(x) for x in MIIS())

last_montly_bong = set(montly_bong)
for _ in range(m - 1):
    last_montly_bong = set(i ^ j for i in montly_bong for j in last_montly_bong)

print(max(last_montly_bong))

# 풀이 2
n, m = MIIS()
montly_bong = list(MIIS())
dp = [[False] * 1024 for _ in range(m)]
# 월봉값을 절댓값으로 저장 & 월봉값 있는 위치에 표시
for i in range(n):
    montly_bong[i] = abs(montly_bong[i])
    dp[0][montly_bong[i]] = True

# 2 ~ m개 선택하는 경우의 수 탐색
for i in range(1, m):
    # 각각 위치 탐색
    for bong in montly_bong:
        for j in range(1024):
            dp[i][j ^ bong] |= dp[i - 1][j]

for i in range(1023, -1, -1):
    if dp[m - 1][i]:
        print(i)
        break

📕코드 해설

풀이 1이 더 간단하고, 빠른 코드이지만, 처음부터 풀이 1에 해당하는 방법으로 떠올리지 못했다. 그래서 풀이 2로 먼저 접근했고, 그 과정에서 풀이 1에 해당하는 아이디어를 많이 얻을 수 있었다.

아래는 풀이 2와 풀이 1에 대한 설명이 순서대로 있다.

 

- 풀이 2

풀이 1, 2 동일하게 모든 월봉값을 절댓값으로 저장한다.

풀이 2에서는 m * 1024 DP 테이블을 활용하여 i개의 월봉 값을 XOR 하여 가능한 j값에 True로 표시했다.

각 과정을 진행할때, 0 ~ 1023 사이의 모든 값과 월봉 값들을 비교하며 A^B^C = (A^B) | (B^C) 이 방식으로 해당 값이 가능한지 연산을 이어갔다.

그리고 1023부터 0까지 거꾸로 탐색하며, 가장 큰 값을 찾아 출력했다

 

- 풀이 1

월봉값을 절댓값으로 저장한 부분까지는 같은데, A^B^C = (A^B)^C 이 방식의 연산으로 이어나갔다.

각 월봉값과 이전에 가능했던 월봉 값을 각각 비교하여 XOR값을 순차적으로 저장했고, 마지막에 그중 최댓값을 출력했다.

 

 

3. 생각 정리

간단한 연산으로만 이루어진 문제이긴 하지만, 그 연산의 활용과, 각 값을 저장하고, 연산을 이어가는 과정에 부족한 부분이 많았다.

XOR 연산과 관련된 문제는 종종 찾아볼 수 있었는데, 이번기회에 XOR에 많은 공부가 되었다.