백준 3649 (로봇 프로젝트) - java

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

3649번: 로봇 프로젝트

문제

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

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

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

 

유형 : 투 포인터

 

접근 방식

• 레고 조각들을 길이의 오름차순으로 정렬
• left = 0 , right = arr.length -1 을 기준으로 arr[left] + arr[right] 값을 기준으로 포인터 이동
  • sum이랑 같은 경우 return
  • sum보다 작은 경우 : left = left + 1
  • sum보다 큰 경우 : right = right - 1

전체 코드

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

public class Main {

    static long l = 0;
    static int n = 0;

    static StringBuilder sb = new StringBuilder();

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String input;
        while((input = br.readLine()) != null) {
            l = Long.parseLong(input) * 10000000;
            n = Integer.parseInt(br.readLine());

            long[] arr = new long[n];

            for (int i = 0; i < n; i++) {
                arr[i] = Long.parseLong(br.readLine());
            }
            Arrays.sort(arr);
            find(0, arr.length - 1, arr);

        }
        System.out.println(sb);
        br.close();
    }

    static void find(int left,int right,long[] arr){
        while(left < right){

            long sum = arr[left] + arr[right];

            if(sum == l){
                sb.append("yes "+arr[left]+" "+arr[right]+"\n");
                return;
            }

            else if(sum > l){
                right = right - 1;
            }

            else{
                left = left + 1;
            }
        }

        sb.append("danger\n");
    }
}