백준 15824번 [너 봄에는 캡사이신이 맛있단다](C++)-yes6686- 티스토리

백준 문제 풀이: 15824 [너 봄에는 캡사이신이 맛있단다]

---

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

문제 설명:

주어진 배열에서 각 부분집합에 대해 가장 큰 원소와 가장 작은 원소의 차이의 합을 구합니다. 단, 이 값을 MOD(1,000,000,007)로 나눈 나머지를 출력합니다.

입력 조건:

• 첫 번째 줄에 원소의 개수 N이 주어집니다. (1 ≤ N ≤ 300,000)
• 두 번째 줄에는 배열의 원소들이 공백으로 구분되어 주어집니다. 배열 원소는 1 이상 1,000,000 이하의 정수입니다.

출력 조건:

• 각 부분집합에서 가장 큰 원소와 가장 작은 원소의 차이의 합을 MOD로 나눈 나머지를 출력합니다.

---

문제 해결 코드

#include <iostream>
#include <algorithm>
#define MOD 1000000007
using namespace std;

int arr[300001];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int N;
    cin >> N;

    for (int i = 0; i < N; i++) {
        cin >> arr[i];
    }

    // 배열 정렬
    sort(arr, arr + N);

    long long t = 1; // 2의 거듭제곱
    long long maxSum = 0, minSum = 0;

    for (int i = 0; i < N; i++) {
        maxSum = (maxSum + arr[i] * t) % MOD;
        minSum = (minSum + arr[N - 1 - i] * t) % MOD;
        t = (t * 2) % MOD;
    }

    // 결과 계산
    long long result = (maxSum - minSum + MOD) % MOD;
    cout << result << '\n';

    return 0; // 프로그램 정상 종료
}

---

코드 설명

위 코드는 정렬된 배열에서 부분집합의 최대값과 최소값의 차이를 효율적으로 계산합니다.

• 정렬: 배열을 오름차순으로 정렬하여 최소값과 최대값을 처리하기 쉽게 만듭니다.
• 2의 거듭제곱:
  • 각 원소가 부분집합에서 최대값으로 사용될 경우의 계수는 2ⁱ입니다.
  • 각 원소가 부분집합에서 최소값으로 사용될 경우의 계수는 2^N-1-i입니다.
• 결과 계산:
  • 최대값의 합과 최소값의 합을 계산한 후, 그 차이를 MOD로 나눕니다.
  • 결과가 음수가 될 수 있으므로 MOD를 더한 후 다시 MOD로 나눕니다.

시간 복잡도 분석:

• 정렬: O(N log N).
• 부분합 계산: O(N).

따라서 전체 시간 복잡도는 O(N log N)입니다.

---

결과

다음은 입력 예시와 출력 결과입니다:

입력:
4
1 3 6 9

출력:
70

위 입력에서는 각 부분집합에 대해 최대값과 최소값의 차이를 계산한 합이 70이 됩니다.

다른 접근 방식이나 개선 사항이 있다면 댓글로 공유 부탁드립니다!