[백준] 20366 같이 눈 사람 만들래? - Java

 

 

 

문제 출저

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

20366번: 같이 눈사람 만들래?

 

 

 

문제 풀이

N개의 눈덩이가 주어집니다. 언니 엘자와 동생 안나는 각각 두 개의 눈덩이를 선택합니다. 눈 사람의 크기는 두 개의 눈덩이 지름의 합입니다. 두 사람의 눈사람 크기 차이가 최소일 경우를 구해야합니다.  N의 크기는 4이상 600이하 입니다.

 

이중 포문과 투 포인터로 문제를 풀었습니다.

이중 포문으로 눈덩이 2개를 골랐습니다. 

2개의 나머지 부분을 투 포인터를 돌려서 최소의 값을 구했습니다.

 

이 때 시간복잡도는 다음과 같습니다.

600 C 2 * 598 = 107,460,600

 

대략 1억이 나오므로 괜찮다고 생각했습니다.

 

 

 

소스코드

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

/*

같이 눈 사람 만들래?
https://www.acmicpc.net/problem/20366

600 c 4 = 5,346,164,850 50억을 넘어 시간 초과가 발생한다. (1억 이상)

포인터를 통해 문제를 푼다.

2 3 5 5 9
2개를 선택하고 2 포인터를 돌린다.
600 C 2 = 179,700
600 C 2 * 598 = 107,460,600

1% 틀림
포인터의 이동 조건을 반대로 줬음..

86% 틀림
투 포인터의 종단 조건을 잘 못 주었다.

 */

public class Main {

    static int answer;

    static int n;
    static int[] snows;


    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

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

        Arrays.sort(snows);
        answer = Math.abs(snows[0] + snows[1] - (snows[2] + snows[3]));

        for(int i = 0; i < n-1; i++) {
            for(int j = i + 1; j < n; j++) {
                twoPointer(i, j);
            }
        }

        System.out.println(answer);

    }

    public static void twoPointer(int i, int j) {
        int snowman1 = snows[i] + snows[j];

        int start = 0;
        int end = n-1;

        while(true) {
            while(start == i || start == j) start++;
            while(end == i || end == j) end--;

            if(start >= end) break;

            int snowman2 = snows[start] + snows[end];

            int result = snowman2 - snowman1;


            if(result >= 0) end--;
            else start++;



            answer = Math.min(answer, Math.abs(result));
        }

    }

}