백준 문제 풀이(1011번) java

문제

https://www.acmicpc.net/problem/1011

풀이

이 문제는 처음과 마지막의 거리가 1로 제한되는 조건이 있다. 이 조건을 만족하며 주어진 거리를 최소한의 횟수로 가는 것이 문제인데 이는 다음과 같이 해결할 수 있다.

위 그림에서 주어진 거리(Distance)는 Count로 갈 수 있는 최대의 거리를 나타내고 있다. 이 문제를 접근할 때 Distance가 제곱수일 때를 기준으로 규칙을 찾아보았다. 각 제곱수 마다 주어진 거리를 가는 최소한의 횟수는 2N - 1이라는 규칙이 있다. 그리고 작은 제곱수와 큰 제곱수 사이에 작은 제곱수 + 자연수보다 큰 거리일 경우 최소 횟수가 증가하는 규칙도 있다. ex) 거리가 12이상이면 (int)Math.sqrt()를 통해 나오는 값은 3이다. 하지만 그렇다고 2N - 1을 적용하여 최소한의 횟수를 5라고 하면 안되고 6이라고 해야한다. 그래서 다음과 같이 조건을 나눠서 문제를 풀이하였다.

int distance = Math.sqrt(주어진거리);
if (주어진 거리 == Math.pow(distance, 2))
else if (주어진 거리 <= Math.pow(distance, 2) + distance)
else

코드

package Category;

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

public class q_1011 {

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        int T = Integer.parseInt(br.readLine());

        for (int i = 0; i < T; i++) {

            StringTokenizer st = new StringTokenizer(br.readLine(), " ");

            int X = Integer.parseInt(st.nextToken());
            int Y = Integer.parseInt(st.nextToken());

            int price = (int) Math.sqrt(Y - X);

            if (Y - X == Math.pow(price, 2)) {
                sb.append(2 * price - 1).append("\n");
            } else if (Y - X <= Math.pow(price, 2) + price) {
                sb.append(2 * price).append("\n");
            } else {
                sb.append(2 * price + 1).append("\n");
            }
        }

        System.out.println(sb);

    }
}