21.07.22 기록

• 백준 알고리즘 1011 풀이

  • 나의 오답(시간초과)
    

    여러 방법을 시도하다가 트리 구조를 생각하며 코드를 간결화해봤지만 시간초과로 풀지 못했다.
    

  import java.io.BufferedReader;
  import java.io.IOException;
  import java.io.InputStreamReader;
  import java.util.StringTokenizer;
  
  public class B1011 {
      public static void main(String[] args) throws IOException {
          BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
          StringTokenizer st;
          StringBuilder sb = new StringBuilder();
  
          int testCase = Integer.parseInt(br.readLine());
          for(int i = 0; i < testCase; i++) {
              st = new StringTokenizer(br.readLine(), " ");
              int x = Integer.parseInt(st.nextToken());
              int y = Integer.parseInt(st.nextToken());
              int cnt = 1;  //맨 처음 k값은 무조건 +1 할 것이므로 카운트 기본값 1
              int k = 1;
  
              x += 1; //맨 처음 k값 무조건 +1 한 것.
              while(x != y) {
                  if(y-x > 2) {
                      x += (k+1);
                      k = (k+1);
                  } else {  //두 수의 차가 2 이하일 때 +1만큼 이동
                      x += 1;
                      k = 1;
                  }
                  cnt++;
              }
              sb.append(cnt).append("\n");
          }
          System.out.println(sb);
      }
  }
  

  
  

  • 해설(메모리 14MB, 시간 124ms로 통과)
    

    풀이를 봐도 규칙을 찾는 것이 어렵게 느껴졌다.
    

    규칙만 잘 찾고 이해한다면 아주 간결한 코드로 풀 수있는 문제였다.
    

  
   import java.io.BufferedReader;
   import java.io.IOException;
   import java.io.InputStreamReader;
   import java.util.StringTokenizer;
  
   public class B1011 {
       public static void main(String[] args) throws IOException {
           BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
           StringBuilder sb = new StringBuilder();
  
           int testCase = Integer.parseInt(br.readLine());
  
           for(int i = 0; i < testCase; i++) {
               StringTokenizer st = new StringTokenizer(br.readLine(), " ");
  
               int X = Integer.parseInt(st.nextToken());
               int Y = Integer.parseInt(st.nextToken());
  
               int distance = Y - X;
               int max = (int)Math.sqrt(distance);
  
               if(max == Math.sqrt(distance)) {
                   sb.append(max * 2 - 1).append('\n');
               }
               else if(distance <= max * max + max) {
                   sb.append(max * 2).append('\n');
               }
               else {
                   sb.append(max * 2 + 1).append('\n');
               }
  
           }
           System.out.println(sb);
       }
   }