백준 16208 자바 - 귀찮음 (BOJ 16208 JAVA)

문제 : boj16208

 

 

1. 우선 그냥 풀어보자.

  결국 현재 막대 크기를 x+y로 나눌 수 있을 때, 비용인 xy들의 합을 최소로 하고 싶은 것이다. 그렇다면 수학적으로 최대한 '작은수 x 큰수'가 되도록 하는것이 최소이다. '중간수 x 중간수'일수록 손해이다. 예를들어 현재 길이가 10일 경우 5x5는 25지만 1x9는 9다. 또한 맨 마지막 막대는 비용이 0이므로 (x+0 이므로 xy = 0) 결국 주어진 n개의 쇠막대를 길이가 짧은 순서대로 나누면 된다(그리디 알고리즘). 내 경우엔 어차피 a_i <= 101 이므로 102개짜리 배열을 만들어서 카운팅했다. 그 후 해당 배열의 인덱스 1부터 101까지 진행하면서, 카운팅된 값 만큼 반복문을 돌면서 x+y로 나누어 직접 계산했다.

 

  이렇게 진행한 코드는 아래와 같다.

※ 이하 코드도 정답코드이나, 아래 '2'에서 더 효율적인 방법을 설명한다. 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    private void solution() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int[] cnt = new int[102];
        StringTokenizer st = new StringTokenizer(br.readLine());

        long sum = 0;
        while (n-->0) {
            int cur = Integer.parseInt(st.nextToken());
            cnt[cur]++;
            sum += cur;
        }

        long answer = 0;
        for (int i = 1; i <= 101; i++) {
            for (int j = 0; j < cnt[i]; j++) {
                answer += i * (sum-=i);
            }
        }
        System.out.println(answer);
    }

    public static void main(String[] args) throws Exception {
        new Main().solution();
    }
}

 

2. 수학적으로 좀 더 빠르게 해보자.

  '1'과 마찬가지로 카운팅까지는 똑같다. 카운팅 해둔 배열이 cnt[] 라고 해보자. 이 때 막대 n개 길이의 합이 s, 현재 보고 있는 cnt 배열의 인덱스가 a, cnt[a]가 c라고 해보자. 그럼 다음과 같이 표현해볼 수 있다. (1+2+...c 는 등차수열의 합 공식을 쓰면 된다)

 

그리고 매번 s는 's -= ca'를 해주면 된다. 최종적으로 답은 다음과 같다. 

  이에 따른 코드는 다음과 같다. 당연하게도 '1'보다 효율적이다. 다만 계산 중간에 '1'보다 수의 범위가 더 커지므로, 오버플로우를 좀 더 주의해야한다.

 

 

코드 : github

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    private void solution() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int[] cnt = new int[102];
        StringTokenizer st = new StringTokenizer(br.readLine());

        int sum = 0;
        while (n-->0) {
            int cur = Integer.parseInt(st.nextToken());
            cnt[cur]++;
            sum += cur;
        }

        long s = sum;
        long answer = 0;
        for (int a = 1; a <= 101; a++) {
            int c = cnt[a];
            answer += 1l*a*(c*s-a*(c*(c+1)/2));
            s -= c*a;
        }
        System.out.println(answer);
    }

    public static void main(String[] args) throws Exception {
        new Main().solution();
    }
}