반응형
https://www.acmicpc.net/problem/15824
15824번: 너 봄에는 캡사이신이 맛있단다
한 줄에 모든 조합의 주헌고통지수 합을 1,000,000,007로 나눈 나머지를 출력한다.
www.acmicpc.net
[ 문제풀이 ]
이 문제에서는 모듈러 연산이 필요하므로 다음 글을 읽고 오시면 좋습니다!
https://rudalsd.tistory.com/45?category=1064608
[ 알고리즘 ] 모듈러 연산(Modular Arithmetic)
오늘은 모듈러 연산에 대해 설명드리겠습니다. 특정 수 M을 넘는 수에 모듈러 연산을 하려면 어떻게 해야 할까요? 모듈러 연산의 특성을 활용하면 쉽게 구할 수 있습니다. [ 동작 원리 ] 정수 A와
rudalsd.tistory.com
어떤 한 수가 조합 내에서 최댓값이 될 때의 개수와 최솟값이 될 때의 개수를 통해 쉽게 정답을 구할 수 있습니다.
먼저 입력받은 수를 오름차순으로 정렬한 후 for문을 돌면서 그 수가 최댓값이 될 때의 조합의 개수는 그 수보다 작은 수의 개수가 i일 때 2^i가 됩니다.
마찬가지로 그 수가 최솟값이 될 때의 조합의 개수는 그 수보다 큰 수의 개수가 j일 때 2^j가 됩니다.
따라서 모든 수에 대해 (2^i - 2^j) * a를 구해서 더해주면 됩니다.
하지만 n의 최댓값이 300,000이므로 일반적인 방법으로는 2^300,000의 수를 구하기는 쉽지 않습니다. 따라서 분할 정복을 활용하여 답을 구해줍니다.
[ 소스 코드 ]
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 | #include<iostream> #include<algorithm> #include<cstring> #define MOD 1000000007 using namespace std; int N; long long arr[300001]; long long comb[300001]; long long ans; long long Comb(int n) //분할 정복을 통한 2의 n승 구하기 { if (comb[n] != -1) return comb[n]; if (n % 2 == 0) { return comb[n] = ((Comb(n / 2) % MOD) * (Comb(n / 2) % MOD)) % MOD; } else { return comb[n] = ((Comb(n - 1) % MOD) * (Comb(1) % MOD)) % MOD; } } int main() { cin >> N; memset(comb, -1, sizeof(comb)); comb[0] = 1; comb[1] = 2; for (int i = 0; i < N; i++) { scanf("%lld", &arr[i]); } sort(arr, arr + N); for (int i = 0; i < N; i++) { //arr[i]가 최대가 되는 조합의 개수에서 arr[i]가 최소가 되는 조합의 개수를 빼고 ans += ((Comb(i) - Comb(N - i - 1) + MOD) % MOD) * (arr[i] % MOD); //거기에 arr[i]를 곱한 것을 ans에 더함 ans %= MOD; } cout << ans; } | cs |
반응형
'백준' 카테고리의 다른 글
| [ 백준 ] 17436번 - 소수의 배수 (C++) (0) | 2022.07.02 |
|---|---|
| [ 백준 ] 16565번 - N포커 (C++) (0) | 2022.07.01 |
| [ 백준 ] 13334번 - 철로 (C++) (0) | 2022.06.29 |
| [ 백준 ] 14725번 - 개미굴 (C++) (0) | 2022.06.28 |
| [ 백준 ] 2533번 - 사회망 서비스(SNS) (C++) (0) | 2022.06.27 |