(Java) 백준 15824 너 봄에는 캡사이신이 맛있단다

고등학교 국어 시간에 배웠던 동백꽃 점순이의 '너 봄 감자가 맛있단다'가 생각나는 상당히 장난스러운 제목으로 기대를 안하고 있었지만 여러 가지를 알고 있어야 풀 수 있는 좋은 문제였다.

 

알고리즘 문제중에는 장난스런 제목과 관계없이 좋은 문제들이 유난히 많은 것 같다. 어쩌면 평범한 이름보다 더..?

 

이런게 개발자의 위트가 아닐까

 

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

 

 

아이디어

각각의 숫자마다 최솟값으로 몇번, 최댓값으로 몇번 사용되는지 생각해보자.

 

예시 (예제 1번)

5 2 8 을 정렬하면 2 5 8 이 된다.

가장 작은 수인 2는 최소값으로 몇번 사용될까

2 2, 2 5, 2 8, 2 5 8 총 4번 사용된다.(자기자신을 선택하는 조합은 어짜피 최소 최대에서 상쇄된다)

최대값으로는 2 2 한번 사용될 것이다.

5는 어떨까

5는 최소값으로 5 5, 5 8 / 2번 사용된다.

최대값으로는 2 5, 5 5 / 2번 사용된다.

 

공식 구하기

여기서 각 자리수마다 최대값으로는 2^i, 최소값으로는 2^(N-i-1) 번 사용된다는 규칙을 유추할 수 있다(i가 0부터 시작한다는 전제로).

문제는 최대값 - 최소값을 구하는 것이므로 val * 2^i - val * 2^(N-i-1) 을 반복문 순회하면서 구해주면 된다.

 

주의 사항

1. 문제 풀이 과정에서 N은 최대 300,000로 최악의 경우 2^300_000이 된다는 것인데 이를 대비하여 1,000,000,007로 나눈 값을 출력하라고 문제에 주어져있다.

거듭제곱을 구할 때 숫자가 커지니 나머지 연산이 필요했다. 하지만 그동안 사용했던 Math.pow() 메서드로는 MOD 연산을 해줄수가 없었다. 그래서 거듭제곱을 저장할 배열을 만들고 직접 모듈러를 계산해서 거듭제곱을 구해줬다.

 

2. 문제가 터질 수 있는 val * 2^i와 val * 2^(N-i-1)에 전부 MOD 연산을 넣어주고 나온 결과값을 더해줄 때도 MOD 연산을 해줬다.

그럼에도 틀렸다. 이유는 음수 MOD 연산에 있었다. 작은값을 계산할때는 val * 2^i - val * 2^(N-i-1) 계산값이 음수가 나오기 마련이다. Java와 C++의 경우 음수를 MOD 연산 해주면 음수로 처리되어 나오는데 큰 문제는 없다고 생각했었지만 착각이었다.

MOD 연산한 양수가 MOD 연산한 음수보다 절대값이 작을 수 있었다.

이 부분은 마지막에 MOD를 더해준뒤 나머지 연산 해주니 해결되었다.

 

import java.io.*;
import java.util.*;

public class Main {

    static final long MOD = 1_000_000_007L;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        int N = Integer.parseInt(br.readLine());
        long[] foods = new long[N];
        st = new StringTokenizer(br.readLine());
        for (int n = 0; n < N; n++) {
            foods[n] = Long.parseLong(st.nextToken());
        }

        long[] pow2 = new long[N];
        pow2[0] = 1;
        for (int i = 1; i < N; i++) {
            pow2[i] = pow2[i-1] * 2 % MOD;
        }

        Arrays.sort(foods);
        // 1. 음식 스코빌지수 * (2^i - 2^(n-i-1))
        // 최댓값 - 최솟값
        long sum = 0;
        for (int n = 0; n < N; n++) {
            long diff = (pow2[n] - pow2[N-n-1]) % MOD;
            long val = foods[n] % MOD * diff;
            sum = (sum + val + MOD) % MOD;
        }

        System.out.println(sum);
    }
}