21.06.02 기록

• 백준 알고리즘 2869 풀이

  • 나의 오답1 (시간초과)
    

    단순히 문제의 흐름을 따라가며 짠 로직이다.
    

  import java.io.BufferedReader;
  import java.io.IOException;
  import java.io.InputStreamReader;
  import java.util.StringTokenizer;
  
  public class B2869 {
      public static void main(String[] args) throws IOException {
          BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
          StringTokenizer st = new StringTokenizer(br.readLine(), " ");
  
          int A =  Integer.parseInt(st.nextToken());
          int B =  Integer.parseInt(st.nextToken());
          int V =  Integer.parseInt(st.nextToken());
  
          int day = 0;
          int loc = 0;
          while(true) {
              day++;
              loc += A;
  
              if(loc < V) {
                  loc -= B;
              }
              else {
                  System.out.println(day);
                  return;
              }
          }
      }
  }
  
  

  
  

  • 나의 오답2 (시간초과)
    

    오답 1로는 시간을 줄일 방법이 없어 보여서 새로운 규칙을 고민했다.
    

    2(A), 1(B), 5(V)를 예로 들자면 2 → 1 → 3 → 2 → 4 → 3 → 5 순으로 변화한다.
    

    이때 빼는 값을 제외하고 보면 2 → 3 → 4 → 5 로 공차가 (A - B) 이다.
    

    나름 오답1 보다는 발전한 규칙을 찾았다고 생각했는데 통과는 못했다.
    

  import java.io.BufferedReader;
  import java.io.IOException;
  import java.io.InputStreamReader;
  import java.util.StringTokenizer;
  
  public class Main {
      public static void main(String[] args) throws IOException {
  
          BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
          StringTokenizer st = new StringTokenizer(br.readLine(), " ");
  
          int A =  Integer.parseInt(st.nextToken());
          int B =  Integer.parseInt(st.nextToken());
          int V =  Integer.parseInt(st.nextToken());
  
          int day = 1;
          int loc = A;
  
          while(loc < V) {
              day++;
              loc += (A-B);
          }
  
          System.out.println(day);
      }
  }
  

  
  

  • 해설 풀이 (메모리 14.1MB, 시간 128ms로 통과)
    

    규칙을 파악해서 반복문 없이 풀이하였다. 규칙에 관한 설명은 링크를 참조하자.
    

  import java.io.BufferedReader;
  import java.io.IOException;
  import java.io.InputStreamReader;
  import java.util.StringTokenizer;
  
  public class B2869 {
      public static void main(String[] args) throws IOException {
          BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
          StringTokenizer st = new StringTokenizer(br.readLine(), " ");
  
          int A = Integer.parseInt(st.nextToken());
          int B = Integer.parseInt(st.nextToken());
          int V = Integer.parseInt(st.nextToken());
  
          int day = (V - B) / (A - B);
          if( (V-B) % (A-B) != 0) { day++; }
          System.out.println(day);
      }
  }