fragment-header
fragment-markdown
홈
로그인
로그아웃
내 블로그
설정
로그인
백준 30961 (C++) 최솟값, 최댓값
최초 업로드: 2025-11-10 02:29:28
최근 수정 시간: 2025-11-10 02:29:28
게시자: rlatjwls3333
카테고리: 백준
조회수: 11
# [Gold III] 최솟값, 최댓값 [문제 링크](https://www.acmicpc.net/problem/30961) ## 문제 설명 <p>수열의 힘은 수열의 최솟값과 최댓값을 곱한 값이다. 길이가 $N$인 수열 $A$가 주어질 때, 이 수열에서 길이가 $1$ 이상인 모든 부분수열 각각의 힘을 구하여 모두 XOR한 값을 구하여라.</p> ## 입력 <p>첫 번째 줄에 $N$이 주어진다. $(1 \le N \le 10^6)$</p> <p>두 번째 줄에 수열 $A$를 이루는 정수 $N$개가 순서대로 주어진다. $(0 \le A_i \le 10^9)$</p> ## 출력 <p>첫 번째 줄에 문제의 답을 출력한다.</p> ## 풀이 정렬해서 모든 쌍을 뽑아내보면, 정렬했을 때 길이 1, 길이 2로 연속된 문자를 뽑아낸 수열 빼고는 전부 짝수 번 등장하여 XOR 하여 사라진다. 결국 정렬해서 길이 1, 길이 2로 뽑아낸 모든 수를 XOR하면 된다. ``` c++ #include<bits/stdc++.h> using namespace std; long long a[1'000'000]; int main() { ios::sync_with_stdio(0); cin.tie(0); int n; cin >> n; for(int i=0;i<n;i++) cin >> a[i]; sort(a, a+n); long long res=0; for(int i=0;i<n-1;i++) res ^= a[i]*a[i+1]; for(int i=0;i<n;i++) res ^= a[i]*a[i]; cout << res; } ```