백준 1011 자바 - Fly me to the Alpha Centauri (BOJ 1011 JAVA)

문제 : boj1011

 

 

  다른 사람 코드들을 보니 규칙을 찾아 수식으로 해결한 경우가 많은 것 같다. 내 경우엔 그리디로 해결했다. x에서 y로 가면서 '최소값'을 구해야 한다. 이 경우, 최선의 선택은 x에서 1로 시작해 무조건 +1로만 진행하는 것이다. 점점 가속해야 가장 최선의 선택임이 자명하다. 하지만 문제는 y에서 도착할 때도 1이어야 한다. 그렇다면 최선의 선택은 다음과 같다.

 

  x에서 계속 +1씩 증가하면서 진행하고, y까지도 계속 -1씩 감소시키면서 감속시키는 것이다. 그럼 반대로 바꿔서 저 '?' 부분을 향해 x와 y에서 동일한 속도로 진행해서 만난다고 생각해보자. 그럼 x쪽에서1, y쪽에서1 -> x쪽에서2, y쪽에서2 -> x쪽에서3, y쪽에서3 이동.. 이런식으로 보면 되겠다. 이 때 저 중간에 뭔가 처리를 해줘야 할 것임을 생각할 수 있겠지만, 어쨌든 이렇게 진행하는 것이 언제나 최소값일 것임은 확실하다(문제에서 제시된 방법 중 가장 빠른(최선의) 방법으로 진행한 것이므로)

 

  그럼 이제 저 ? 부분 사이에만 '잘' 처리해주면 된다. 예를들어 x가 0, y가 12라 해보자.

0. x=0, y=12

1. x=1, y=11

2. x=3, y=9

3. x=6, y=6

-> 이보다 빠른 방법은 없다. 속도를 계속 증가시켰고, 중간에서 딱 만났다. 총 x3회 y3회로 6회가 답이다.

 

  x가 0, y가 10인 경우

S. x=0, y=10

1. x=1, y=9

2. x=3, y=7

3. x=6, y=4

-> 서로 2만큼 어긋났다. 하지만 어쨌든 6회보다 빠른 방법은 없다. 최선으로 달려서 6회이므로, 저 사이에 '2'만큼의 어긋남은 딱히 문제가 안되는게 중간중간 한번씩 +1을 해주지 않고 속도를 늦춰주면 어떻게든 맞출 수 있다. 그러니 '2'만큼을 맞추는 부분에 대해서는 신경쓰지 않아도 된다.

 

S. x=0, y=9 인 경우

1. x=1, y=8

2. x=3, y=6

3. x=6, y=3

-> 이번엔 최종적으로 도달했던 이동거리인 '3'만큼의 차이가 나버렸다. 이 경우엔 어떻게 될까? 이 경우 x나 y가 한번 덜 가도 된다. 이미 x가 3만큼 갔을 때 x=6이 되어 y=6과 바로 만나버리기 때문이다. 그러므로 x=3회, y는2회로 5회가 된다.

 

-> 물론 내 경우 x와 y 양방향에서 서로 출발한다고 바꿔 생각했으므로 이게 말이 된다. 하지만 실제로 이 문제는 x에서 y로만 가야 한다. 그럼 왜 5회가 가능할까? 처음 이동거리가 1이고, 최선을 다해 n번 이동 했을 때 이동거리도 마찬가지로 n이다. 따라서 최대 n의 차이는 1회를 줄이더라도 어떻게든 중간에서 만나게 할 수 있다.

 

 

최종적으로 정리해보면 로직은 다음과 같다.

A. 최선의 선택을 하면 (따라서 그리디) x는 언제나 +1을 하고, 중간지점에서 y를 향해 언제나 -1을 하면 된다. 따라서 생각을 좀 바꿔서 x와 y에서 각각 중간을 향해 언제나 +1을 한다고 봐도 된다. 이 경우 n회 진행 시 총 2n번으로 카운팅하면 된다. (x에서 n번, y에서 n번)

 

B. x가 y값보다 크거나 같아질 때 까지 위의 과정을 진행한다.

 

C. 이 때 x와 y의 차이가 'B'에서 마지막으로 이동했던 거리(=n)보다 크다면, 1회를 빼도 된다. (코드 14line)

 

 

코드 : github

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    private int getMinCnt(int x, int y) {
        int i = 0;
        while (x<y) {
            x += ++i;
            y -= i;
        }
        return x>=y+i ? 2*i-1 : 2*i;
    }

    private void solution() throws Exception {
        int t = Integer.parseInt(br.readLine());
        StringBuilder sb = new StringBuilder();
        while (t-->0) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());
            sb.append(getMinCnt(x, y)).append('\n');
        }
        System.out.print(sb);
    }

    public static void main(String[] args) throws Exception {
        new Main().solution();
    }
}