boj3649 로봇 프로젝트_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|가 가장 큰 것을 출력한다.

나의 풀이

• lego 배열의 인덱스를 이진탐색하여 풀었는데, 좀더 자세히 풀이에 대해서 얘기해보겠다.
  • lego 배열을 N 사이즈 만큼 생성해서 레고들을 넣고, 정렬시킨다.
  • lego 배열에서 for문을 돌려 i 를 선택하고, i 부터 N 까지 이진탐색을 통해서 X 값을 만드는 경우를 구한다. X 와 같은 경우를 찾았을 때 answer 값과 비교하여 더 큰경우, l1 과 l2를 갱신해준다.
  • for문을 다 돌린 후, StringBuilder 에 값을 넣고, 출력 후에는 setLength(0) 으로 길이를 줄여버린다.
• 이 문제에서 제일 까다로운 부분은 사실상 테스트케이스 입력 갯수가 사전에 정해지지 않는다는 것이었다. 그래서 방법을 찾아본 결과 이 분의 블로그를 통해서 방법을 찾았고, 나는 while((x=br.readLine())!=null 이렇게 작성하여 해당 문제를 해결하였다.
• 핵심 코드

  while((x=br.readLine())!=null) {
              int X = Integer.parseInt(x) * 10000000;
              int N = Integer.parseInt(br.readLine());
              int[] lego = new int[N];
              int answer = -1;
              int l1 = -1;
              int l2 = -1;
              for (int i = 0; i < N; i++) {
                  lego[i] = Integer.parseInt(br.readLine());
              }
              Arrays.sort(lego);
              for (int i = 0; i < N; i++) {
                  int now = lego[i];
                  int left = i;
                  int right = N - 1;
                  while (left <= right) {
                      int mid = (left + right) / 2;
                      if (mid != i) {
                          if (lego[mid] == X - now) {
                              if (answer < Math.abs(now - lego[mid])) {
                                  answer = Math.abs(now - lego[mid]);
                                  l2 = Math.max(now, lego[mid]);
                                  l1 = Math.min(now, lego[mid]);
                              }
                              left = mid + 1;
                          } else if (lego[mid] > X - now) {
                              right = mid - 1;
                          } else if (lego[mid] < X - now) {
                              left = mid + 1;
                          }
                      } else {
                          left = mid + 1;
                      }
                  }
              }
              if (answer != -1) {
                  sb.append("yes ").append(l1).append(" ").append(l2);
              } else {
                  sb.append("danger");
              }
              System.out.println(sb.toString());
              sb.setLength(0);
          }

• 전체 코드

  package Baekjoon.java.gold;
  
  import java.io.BufferedReader;
  import java.io.InputStreamReader;
  import java.util.Arrays;
  
  public class boj3649 {
      public static void main(String[] args) throws Exception {
          BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
          StringBuilder sb = new StringBuilder();
          String x;
          while((x=br.readLine())!=null) {
              int X = Integer.parseInt(x) * 10000000;
              int N = Integer.parseInt(br.readLine());
              int[] lego = new int[N];
              int answer = -1;
              int l1 = -1;
              int l2 = -1;
              for (int i = 0; i < N; i++) {
                  lego[i] = Integer.parseInt(br.readLine());
              }
              Arrays.sort(lego);
              for (int i = 0; i < N; i++) {
                  int now = lego[i];
                  int left = i;
                  int right = N - 1;
                  while (left <= right) {
                      int mid = (left + right) / 2;
                      if (mid != i) {
                          if (lego[mid] == X - now) {
                              if (answer < Math.abs(now - lego[mid])) {
                                  answer = Math.abs(now - lego[mid]);
                                  l2 = Math.max(now, lego[mid]);
                                  l1 = Math.min(now, lego[mid]);
                              }
                              left = mid + 1;
                          } else if (lego[mid] > X - now) {
                              right = mid - 1;
                          } else if (lego[mid] < X - now) {
                              left = mid + 1;
                          }
                      } else {
                          left = mid + 1;
                      }
                  }
              }
              if (answer != -1) {
                  sb.append("yes ").append(l1).append(" ").append(l2);
              } else {
                  sb.append("danger");
              }
              System.out.println(sb.toString());
              sb.setLength(0);
          }
      }
  }

결과