[라인] 2019 인턴 코딩테스트

문제보기

내일 라인 인턴 코테가 있다. 대비용으로 라인 블로그에 올라온 문제를 풀어보았다.

어떻게 더 시간을 줄일 수 있는지 모르겠다. 예제 하나만 통과된거라…

경우의 수가 많아지면 분명 시간초과 날텐데 ㅠㅠ

import java.util.*;
import java.io.*;
class Jump{
  int c; // 코니 위치
  int b; // 브라운 위치
  int d; // 코니의 점프력
  int t; // 현재 시간
  Jump(int c, int b, int d, int t){
    this.c = c; 
    this.b = b;
    this.d = d;
    this.t = t;
  }
}

public class Main{
  static void bfs(int x, int y){
    Queue<Jump> q = new LinkedList<>();
    q.add(new Jump(x, y, 1, 0));

    while(!q.isEmpty()){
      Jump j = q.remove();
      int c = j.c;
      int b = j.b;
      int d = j.d;
      int t = j.t;

      if( c == b ){ // 잡았다 요놈!
        System.out.println(t);
        return;
      }
      t++; // 시간 1초 지남
      c += d++; // 코니 이동 
      
      // 브라운 이동 
      if( c <= 200000 ){ 
        if(b-1 >= 0){
          q.add(new Jump(c, b-1, d, t));
        }
        if(b+1 <= 200000){
          q.add(new Jump(c, b+1, d, t));
        }
        if(b*2 <= 200000){
          q.add(new Jump(c, b*2, d, t));
        }
      }

    }
    System.out.println(-1); // q가 비었다면 -1 불가능
  }
  public static void main(String []args) throws IOException{
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer st = new StringTokenizer(br.readLine());
    int c = Integer.parseInt(st.nextToken());
    int b = Integer.parseInt(st.nextToken());
    if( c == b ){
      System.out.println(0); return;
    }
    bfs(c, b);
  }
}