[Python] 30961번 최솟값, 최댓값

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

30961번: 최솟값, 최댓값

---

 

24/03/18

 

 

XOR의 성질을 이용한 간단한 수학 문제다.

---

 

문제 접근 방식:

 

 

문제의 요구 사항은 수열 $A$가 주어졌을 때, $A$의 부분 수열 $B$의 최댓값과 최솟값을 곱한 값을 $C$라고 하면, $A$의 모든 부분 수열에서 나오는 $C$의 값을 모두 XOR한 값을 구하는 것이다.

 

즉, 다음과 같은 수식으로 나타낼 수 있다.

 

$$\bigoplus_{B \subset A} ( \max B \times \min B )$$

 

부분 수열의 최댓값과 최솟값을 문제에서 요구하고 있기 때문에, 주어진 수열을 정렬해보자.

 

예를 들어, 정렬된 $A$가 다음과 같이 $10$개의 정수로 구성된 수열이라고 해보자.

 

$$a_0, a_1, a_2, a_3, a_4, a_5, a_6, a_7, a_8, a_9$$

 

부분 수열 $B$의 최솟값이 $a_0$이고 최댓값이 $a_0$인 경우는 부분 수열 $B$가 $\{ a_0 \}$인 경우뿐이다.

마찬가지로, 부분 수열 $B$의 최솟값이 $a_0$이고 최댓값이 $a_1$인 경우는 부분 수열 $B$가 $\{ a_0, a_1 \}$인 경우뿐이다.

 

부분 수열 $B$의 최솟값이 $a_0$이고 최댓값이 $a_2$인 경우는 부분 수열 $B$에 $a_1$이 포함되냐 포함되지 않냐로, 총 $2$가지 경우가 있다.

 

여기서 중요한 XOR의 성질이 사용되는데, 같은 수를 짝수 번 XOR하면 $0$이 된다는 점이다. 다시 말해, XOR을 하지 않은 것과 동일하다는 뜻이다.

 

따라서 최솟값이 $a_0$이고 최댓값이 $a_2$인 경우는 짝수 번 XOR되므로, 이 경우는 XOR을 하지 않은 것과 동일하다.

 

마찬가지로, 부분 수열 $B$의 최솟값이 $a_0$이고 최댓값이 $a_3$인 경우는 부분 수열 $B$에 $a_1$이 포함되냐, 포함되지 않냐로, $a_2$이 포함되냐 포함되지 않냐로, 총 $4$가지 경우가 있다.

 

마찬가지로, 이 경우도 짝수 번 XOR되므로, XOR하지 않은 것과 동일하다.

 

이를 일반화하면, 어떤 부분 수열 $B$의 최댓값과 최솟값이, 정렬했을 시의 인덱스가 $2$이상 차이 난다면, 똑같은 최댓값과 최솟값을 가지는 부분 수열이 짝수 번이 나오므로, XOR을 하지 않은 것과 동일하다.

 

따라서, 우리는 수열 $A$를 정렬한 뒤, 인덱스 차이가 $0$또는 $1$이 나오는, 즉, $a_i \times a_i$와 $a_i \times a_{i+1}$들만 모두 XOR해주면 충분하다는 결론을 얻어낼 수 있다.

 

이를 그대로 코드로 구현하면 된다.

   

---

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

# 30961번 최솟값, 최댓값
# 정렬, 수학
import sys
input = sys.stdin.readline

N = int(input())
A = sorted(map(int, input().rstrip().split()))
ans = 0
for i in range(N):
    ans ^= A[i]*A[i]
for i in range(N-1):    
    ans ^= A[i]*A[i+1]
print(ans)