[백준 - 3649[GOLD 5][해설 X] - 로봇 프로젝트 (JAVA)

문제 링크

---

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

 

문제

---

상근이와 선영이는 학교 숙제로 로봇을 만들고 있다. 로봇을 만들던 중에 구멍을 막을 두 레고 조각이 필요하다는 것을 깨달았다.

구멍의 너비는 x 센티미터이고, 구멍에 넣을 두 조각의 길이의 합은 구멍의 너비와 정확하게 일치해야 한다. 정확하게 일치하지 않으면, 프로젝트 시연을 할 때 로봇은 부수어질 것이고 상근이와 선영이는 F를 받게 된다. 구멍은 항상 두 조각으로 막아야 한다.

지난밤, 상근이와 선영이는 물리 실험실에 들어가서 레고 조각의 크기를 모두 정확하게 재고 돌아왔다. 구멍을 완벽하게 막을 수 있는 두 조각을 구하는 프로그램을 작성하시오.

 

입력

---

입력은 여러 개의 테스트 케이스로 이루어져 있다.

각 테스트 케이스의 첫째 줄에는 구멍의 너비 x (1 ≤ x ≤ 20, x는 정수)가 주어진다. x의 단위는 센티미터이다.

다음 줄에는 물리 실험실에 있는 레고 조각의 수 n이 주어진다. (0 ≤ n ≤ 1000000)

다음 n개의 줄에는 레고 조각의 길이 ℓ이 주어진다. ℓ은 양의 정수이며, 단위는 나노미터이다. 블록의 길이는 10 센티미터 (100000000 나노미터)를 넘지 않는다.

 

출력

---

각 테스트 케이스마다 한 줄에 하나씩, 구멍을 완벽하게 막을 수 있는 두 조각이 없다면 'danger'를 출력한다. 막을 수 있는 경우에는 'yes ℓ1 ℓ2'를 출력한다. (ℓ1 ≤ ℓ2)

정답이 여러 개인 경우에는 |ℓ1 - ℓ2|가 가장 큰 것을 출력한다.

 

해결 코드

---

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

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        String input = "";

        while((input = br.readLine())!=null && !input.isEmpty()){
            //cm를 nm로 변경
            long x = Integer.parseInt(input) * 1_000_000_000L / 100;
            int n = Integer.parseInt(br.readLine());

            long[] lego = new long[n];

            for(int i=0;i<lego.length;i++){
                lego[i] = Long.parseLong(br.readLine());
            }

            Arrays.sort(lego);

            int[] answer = new int[]{0,0};
            boolean valid = false;
            int l = 0;
            int r = n-1;

            //투포인터를 이용해 두수의 합이 x인 것을 탐색
            while(l<r){
                long sum = lego[l]+lego[r];

                //두 수의 합이 x인 경우
                if(sum == x){
                    valid = true;

                    //두 수의 절대값이 더 크거나 같은것을 찾은 경우 해당 경우의 수를 대입
                    //원래는 큰 것만해도 가능하나 초기값을 0,0으로 고정하여 차이가 0이 나온다.
                    //이 때 lego[l]과 lego[r]이 모두 값이 같아 차이가 0인 경우 부등호가 <이면 업데이트되지 않기 때문에 <=로 설정한다.
                    if(lego[answer[1]] - lego[answer[0]]  <= lego[r] - lego[l]){
                        answer[0] = l;
                        answer[1] = r;
                    }
                }

                if(sum > x){
                    r--;
                }else{
                    l++;
                }
            }

            if(!valid){
                System.out.println("danger");
            }else{
                System.out.println(String.format("yes %d %d",lego[answer[0]],lego[answer[1]]));
            }
        }
    }
}

 

 

실행 결과

---

 

팁

---

• 두 수의 합은 두 포인터로 해결할 수 있다.
• 입력값을 무한히 받기 위해선 (String str = br.readLine()) != null을 이용하자