[백준/Java] 17954 : 투튜브

📌 문제 정보

• 번호: 17954
• 제목: 투튜브
• 난이도: Gold 1
• 분류: 수학, 그리디

---

💡 접근 방식

2×N 배열에 1~2N을 배치해서 점수의 합을 최대화하는 문제입니다.
큰 수를 앞쪽 열에 배치할수록 이후 열에서 계속 더해지므로 최대한 앞에 배치해야 합니다.
배치 식을 직접 생각하지 못해서 찾아봤습니다.

---

🔹 1단계 – 점수 계산 방식

size를 전체 합에서 하나씩 빼가면서 각 열의 가중치를 곱해 누적

long size = ((2L * N) * ((2L * N) + 1)) / 2;

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

---

🔹 2단계 – 배치 전략

2N-1, 2N  →  1열 (가장 큰 수 두 개를 맨 앞에)
2N-2       →  2열
...

구체적으로

1행: [2N-3, ..중간 작은 수.., 2N-2]
2행: [2N-1, ..중간 작은 수.., 2N  ]

---

🔹 3단계 – 배치 공식

arr[0][0] = 2 * N - 3;
arr[0][N - 1] = arr[0][0] + 1;   // 2N-2

arr[1][0] = 2 * N - 1;
arr[1][N - 1] = arr[1][0] + 1;   // 2N

// 중간 칸은 작은 수들로 채우기
for (int j = 1; j <= N - 2; j++) {
    arr[i][j] = arr[0][0] - ((i * (N - 2)) + j);
}

---

💻 핵심 코드

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

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

---

⏳ 복잡도 분석

• 시간 복잡도: O(N)
• 공간 복잡도: O(N)

---

📄 전체 코드

package B17954;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

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());
        StringBuilder sb = new StringBuilder();

        int[][] arr = new int[2][N];
        long size = ((2L * N) * ((2L * N) + 1)) / 2;
        long answer = 0;

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

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

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

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

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