[백준 - 17954번] 투튜브 - Java

문제 링크

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

문제

티어: 골드 2
알고리즘: 그리디

입력

첫째 줄에 양의 정수 N이 주어진다. (1 ≤ N ≤ 10,000)

출력

첫째 줄에 최소의 부패도를 출력한다.

둘째 줄과 셋째 줄에 최소의 부패도를 가지는 사과의 배치를 출력한다. 만약 최소의 부패도를 가지는 사과의 배치가 여러가지 존재할 경우, 그 중 아무거나 출력한다.

풀이

총 부패도를 최소가 되게 하려면 당연히 크기가 큰 사과부터 우선적으로 꺼내야 한다.

그런데 4개의 구멍 중 가장 작은 사과부터 꺼낼 수 있기 때문에 무작정 사이즈가 큰 사과부터 꺼낼 수는 없다.

그래서 처음에 꺼낼 수 있는 가장 큰 사이즈의 사과는 2N - 3이 된다. 왜냐하면 나머지 구멍을 2N ~ 2N - 2로 배치해야 그나마 큰 사이즈인 2N - 3을 꺼낼 수 있기 때문이다.
예를 들어 다음과 같이 말이다.
3 2 4
5 1 6

여기서 3을 꺼내고 나면 안쪽 사과들은 나머지 구멍의 사과보다 작을 수 밖에 없다. 그래서 그 다음으로 큰 사과들을 배치해야 한다. 2N - 3, 2N - 4, 2N - 5...와 같이 말이다.

여기서 중요한 점은 2N - 3의 반대쪽 구멍은 2N - 2가 위치해야 한다. 그래야 2N - 2가 꺼내지고 나서 2N - 1을 꺼낼 수 있기 때문이다.

예를 들어
3 2 5
4 1 6 으로 배치하면 3 -> 2 -> 4 -> 1 -> 5 -> 6이 된다.

그런데
3 2 4
5 1 6 으로 배치하면 3 -> 2 -> 4 -> 5 -> 1 -> 6이 된다.

당연히 2N - 1 (앞에서는 5)를 꺼내고 나서 그 다음으로 큰 사이즈의 사과를 꺼내야 한다.
이를 일반화하면 2N - 1, N - 2, N - 3 ... 1이 된다.
직접 N을 대입해보면 이해하는데 어렵지 않다.

이 풀이의 시간복잡도는 O(N)이다.

소스 코드

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

public class Main {
    static int N;
    public static void main(String args[]) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        int[][] apple = new int[2][N];
        long size = ((2 * N) * ((2 * N) + 1)) / 2;
        long answer = 0;

        if (N == 1) {
            apple[0][0] = 1;
            apple[1][0] = 2;
        } else {
            apple[0][0] = 2 * N - 3;
            apple[0][N - 1] = apple[0][0] + 1;

            apple[1][0] = 2 * N - 1;
            apple[1][N - 1] = apple[1][0] + 1;
            for (int i = 0; i <= 1; i++) {
                for (int j = 1; j <= N - 2; j++) {
                    apple[i][j] = apple[0][0] - ((i * (N - 2)) + j);
                }
            }

        }

        for (int i = 0; i <= N - 1; i++) {
            size -= apple[0][i];
            answer += (i + 1) * size;
        }

        for (int i = 0; i <= N - 2; i++) {
            size -= apple[1][i];
            answer += (N + i + 1) * size;
        }

        StringBuilder sb = new StringBuilder();
        sb.append(answer).append("\n");
        for (int i = 0; i < 2; i++) {
            for (int j = 0; j < N; j++) {
                sb.append(apple[i][j]).append(" ");
            }
            sb.append("\n");
        }
        System.out.println(sb.toString().trim());
    }
}