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

 

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

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

문제에서...
(다음 월봉의 절댓값) = 이전 N개의 월봉 중 중복을 허용해 M개를 골라 절댓값들을 bitwise xor 한 것 중 최대
라고 되어있다.

처음 문제를 보게 될때는 N개중 M개를 고르는 것으로 보여 조합으로 생각할 수도 있다.
하지만 경우의 수가 너무 많아지게 되어 풀 수 없으며 다른 방법을 찾아야만 한다.

먼저 문제를 이해하기 위해 주어진 예시로 설명을 하겠다.
만약 숫자가 1,2,3가 있고 3개를 고르는 경우를 예시로 들면...

(괄호 안의 숫자는 2진수를 의미한다.)

- 1개를 고르는 경우: 3(11)
- 2개를 고르는 경우: 1^2 = 3(11)
- 3개를 고르는 경우: 1^1^3 = 3(11)

따라서 3(11)이 정답이다.

하지만 각 순간의 최대값만을 이용해 구했다면 3개를 고르는 경우는 2개를 고르는 경우의 최대값인 3을 이용해야만 하므로
위의 결과가 아닌 1^2^1과 같이 나오게 될 것이며,
따라서 2(10)이 나오게 될 것이다.
고로 이 문제는 배낭문제(Knapsack Problem)로 풀어야 한다.

문제를 푸는덴 다양한 방법이 있겠지만 DP를 사용해 풀어보았다.
DP로 풀자고 마음을 먹었고 생각나는 방법은 두가지가 있었다.

Set을 이용한 방법과 1024개의 bool 배열을 이용하는 방법이다.

---

1. Set - 내가 푼 방법

각 숫자들의 연산은 사칙연산이 아닌 XOR이기에 연산 결과는 더 큰 자리수를 만들 수 없다.
또한 값이 중복되어도 최종 결과는 똑같다. (2^2^3 = 1^1^3)
따라서 중복된 값이어도 연산 결과는 동일하므로 중복제거를 하는 것이 바람직하다.
이때 중복제거를 위해 set의 특성을 사용하였다.

ex1) N = 3, M = 2, A = [9,4,10]
숫자는 2진수로 표기하며 0행의 숫자들은 배열 A를 의미한다.
0열의 숫자들은 M-1행까지의 연산에서 얻을 수 있는 모든 결과값을 의미한다.

	1001	0100	1010
1001	0000	1101	0011
0100	1101	0000	1110
1010	0011	1110	0000

=> 0000, 0011, 1101, 1110 의 결과를 얻을 수 있다.
따라서 최대값은 14(1110)

ex2) N = 3, M = 3, A = [9,4,10]
위 결과에서 얻은 결과에 대해 한번 더 연산을 진행한다.
0열의 숫자는 2행까지의 연산에서 얻을 수 있는 모든 결과값을 의미한다.

	1001	0100	1010
0000	1001	0100	1010
0011	1011	0111	1001
1101	0100	1001	0111
1110	0110	1010	0100

=> 0100, 0111, 1001, 1010 의 결과를 얻을 수 있다.
따라서 최대값은 10(1010)

결국 k개월의 연산결과는 k-1개월까지의 결과와 이번달의 결과를 연산한 것이 된다.
구현은 맨 아래를 참고.

2. 1024개의 bool 배열을 사용

 문제의 조건을 보게 되면 A의 최대값은 2^10보다 작다.

즉 A에 들어가는 원소는 0부터 1023까지 인 것을 이용하는 것이다. (1024개의 배열로도 충분하다.)

이러한 성질을 이용해 dp배열을 만들면 아래와 같이 된다.

dp[i][j]는 다음과 같이 정의한다.
i : 월(month)
j : 숫자 자체를 의미
bool 타입으로 만들어 각 숫자 dp[i][j]가 True라면 j가 존재하는 것이며 dp[i][j]가 False라면 j가 존재하지 않는 것으로 판단한다.

만약 dp[i-1][j]에 숫자가 존재한다면, i행에 해당하는 j에 대해 True로 갱신해주어야한다.
이를 위해 모든 A의 원소에 대해 j와 연산한 결과에 해당하는 열을 True로 바꿔준다.

dp[i][ j ^ abs([A[k]) ] = True

이렇게 구한 dp 배열을 가장 마지막 행인 1023부터 감소하는 반복문을 돌려주며 True인 값을 찾아준다.
만약 True값을 발견하면 해당 j가 최대값이기 때문에 j를 출력하고 반복문을 break해주면 된다.

구현은 생략

---

<구현 > - [Python] set을 사용한 풀이

n,m = map(int,input().split())
arr = list(map(int,input().split()))
this_month = []



# this_month 배열에 입력받은 값을 절대값을 취해 넣어준다.

for item in arr:
this_month.append(abs(item))



# month라는 이름의 Set을 만든다.

# 이때 month는 1개월차의 결과를 의미한다.
month = set(this_month)



# 위의 ex2)에서 보였던 과정을 M-1번 반복해준다.
for _ in range(m-1):
month = set(i^j for i in this_month for j in month)


# 출력

print(max(month))

백준 비트코인은 신이고 나는 무적이다