백준 12993 - 이동3 (자바 - 그리디)

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

12993번: 이동3

 

* 문제 요약

동혁이는 크기가 무한대인 평면 위에 원점(0, 0) 에 올라가있다.

동혁이는 이동을 단계별로 하면서 (x, y) 로 이동하려고 한다. 단계는 0 부터 시작한다.

각 단계마다 동혁이는 두 방향 오른쪽 (x - 좌표 증가) 과 위 (y - 좌표 증가) 중에서 하나를 고른 다음 3^k 만큼 이동한다.

이때 k 는 단계 번호이다.

이동하지 않고 단계를 건너 뛰는 것은 불가능하다.

x 와 y 가 주어졌을 때 (0, 0) 에서 (x, y) 를 갈 수 있는지 없는지 구하는 프로그램을 작성하시오.

 

* 입력

첫째 줄에 x 와 y 가 주어진다. (0 <= x, y <= 1,000,000,000)

 

* 출력

(0, 0) 에서 (x, y) 를 갈 수 있으면 1을, 없으면 0 을 출력한다.

 

* 예시

 

* 해결 과정

x 와 y 둘 다 0 이 입력될 경우 즉시 1을 출력해준다.

만약 그렇지 않을 경우 아래와 같이 로직을 수행한다.

1. 0단계부터 단계를 1씩 늘려가며 단계별로 3의 제곱수를 구한 다음, x, y 중 더 큰 수와 비교하여 현재 제곱수가 더 작을 경우 단계를 계속해서 올리고, 제곱수가 더 클 경우 단계를 1단계 내린 다음 첫번째 반복문을 종료한다.

2. 첫번째 반복문에서 구한 단계에서부터 역으로 0 단계까지 내려가며 3의 제곱수를 구하는 동시에 x 와 y 중 더 큰 값에서 현재 단계의 3의 제곱수를 빼준다. 만약 도중에 둘 중 하나가 0 보다 작아지면 반복문을 종료시킨다.

3. 최종적으로 x, y 둘 다 0 이 될 경우 (0, 0) 에서 (x, y) 로 이동 할 수 있다는 뜻이므로 1을 출력시키고 그렇지 않을 경우 0 을 출력시킨다.

 

* 코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

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

    private void solution() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        String[] input = br.readLine().split(" ");
        int x = Integer.parseInt(input[0]);
        int y = Integer.parseInt(input[1]);

        int index = 0;
        if (x == 0 && y == 0) {
            bw.write(1 + "\n");
        } else {
            int big = Math.max(x, y);
            long threeNumber = 0;
            while (true) {
                threeNumber = (long) Math.pow(3, index);
                if (big > threeNumber)
                    index++;
                else if (big < threeNumber) {
                    index--;
                    break;
                } else if (big == threeNumber) {
                    break;
                }
            }

            for (int i = index; i >= 0; i--) {
                if (x > y)
                    x -= Math.pow(3, i);
                else
                    y -= Math.pow(3, i);

                if (x < 0 || y < 0)
                    break;
            }

            if (x == 0 && y == 0) {
                bw.write(1 + "\n");
            } else {
                bw.write(0 + "\n");
            }
        }

        bw.flush();
        bw.close();
        br.close();
    }
}

 

현재 상황에서 최적의 해답을 선택한다. -> 올라갈 수 있는 최대 단계를 구한 이후 해당 단계부터 0 단계까지 반복문을 통해 내려가며 x, y 중 더 큰 값을 대상으로 현재 단계기준 이동거리를 빼준다.

선택된 해답이 조건을 만족하는지 검사한다. -> 반복문을 수행하다가 0 단계가 되거나, x, y 둘 중 하나가 음수가 되지 않는 한 (0, 0) 에서 (x, y) 까지 이동할 수 있는지 알 수 없으므로 반복문을 계속 수행한다.

 

위의 과정을 거쳐 문제를 해결하였으므로 그리디 알고리즘에 해당된다.