[BOJ] 백준 20366 : 같이 눈사람 만들래? (java)

🧪 20366 같이 눈사람 만들래?

---

난이도 : 🌟 골드 3
유형 : 투포인터

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

 

📝 문제

---

언니! 똑...똑똑...똑똑! 같이 눈사람 만들래~? ♪

언니 엘자와 동생 안나에게는 N개의 눈덩이가 있다. 각 눈덩이 i (1 ≤ i ≤ N)의 지름은 Hi 이다. 하나의 눈사람은 두 개의 눈덩이로 구성되며, 눈덩이 하나를 아래에 두고 그 눈덩이보다 크지 않은 다른 눈덩이를 쌓아올리는 방식으로 만들 수 있다. 이때, 눈사람의 키는 두 눈덩이 지름의 합과 같다.

엘자와 안나는 눈덩이 N개 중 서로 다른 4개를 골라서 눈사람을 각각 1개씩, 총 2개를 만들려고 한다. 두 자매는 두 눈사람의 키의 차이가 작을수록 두 눈사람의 사이가 좋을 것이라고 믿는다. 우리는 엘자와 안나가 가장 사이좋은 두 눈사람을 만들기 위해서 도와주려고 한다.

주어진 N개의 눈덩이를 이용하여 만들 수 있는 두 눈사람의 키 차이 중 최솟값을 구하는 프로그램을 작성하시오.

 

 

입력

 

첫째 줄에 N (4 ≤ N ≤ 600)이 주어진다.

둘째 줄에는 각 눈덩이 i (1 ≤ i ≤ N)의 지름을 의미하는 정수 Hi (1 ≤ Hi ≤ 109)가 공백으로 구분되어 주어진다.

출력

 

만들 수 있는 두 눈사람의 키 차이 중 최솟값을 나타내는 정수를 출력하라.

 

🧐 핵심 로직

---

1. 두 스노우맨의 높이 차이가 가장 적은 경우를 찾기 위해 완전탐색과 투포인터를 결합해 접근한다.

 

2. 외부 반복문에서는 두 스노우맨 중 하나를 구성할 두 눈사람의 크기를 고정한다.

    2 - a) 현재 선택된 두 눈사람 크기를 합산해 snowMan1을 구성한다.

 

3. 내부 투포인터를 이용해 나머지 두 눈사람으로 snowMan2를 구성한다.

    3 - a) 투포인터의 시작과 끝은 배열의 처음과 끝에서 시작하며, 고정된 눈사람과 중복되지 않도록 처리한다.

    3 - b) 두 눈사람의 크기 차이를 계산해 res를 갱신하고, snowMan1과 snowMan2의 상대적 크기를 비교해 투포인터의 위치를 조정한다.

        3 - a - 1) snowMan2가 크다면 end를 줄이고, 작다면 start를 늘린다.

        3 - b - 2)두 눈사람 크기가 같으면 차이가 0이므로 바로 종료한다.

 

4. 모든 경우를 탐색한 후 최소값 res를 출력한다.

 

💻 최종 코드 (224 ms)

---

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

public class Main {

    static int n, res;
    static int[] diameters;
    public static void main(String[] args) throws Exception {

//        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedReader br = new BufferedReader(new FileReader("input.txt"));

        n = Integer.parseInt(br.readLine());
        res = Integer.MAX_VALUE;

        diameters = new int[n];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) {
            diameters[i] = Integer.parseInt(st.nextToken());
        }

        Arrays.sort(diameters);

        twoPointer();

        br.close(); 
    }

    private static void twoPointer() {

        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                int snowMan1 = diameters[i] + diameters[j];
                int start = 0;
                int end = n - 1;

                while (start < end) {

                    if (start == i || start == j) {
                        start++;
                        continue;
                    }

                    if (end == i || end == j) {
                        end--;
                        continue;
                    }

                    int snowMan2 = diameters[start] + diameters[end];
                    res = Math.min(res, Math.abs(snowMan2 - snowMan1));

                    if (snowMan1 < snowMan2) {
                        end--;
                    } else if (snowMan1 > snowMan2) {
                        start++;
                    } else {
                        System.out.println(0);
                        return;
                    }
                }
            }
        }

        System.out.println(res);
    }
}