[자바] 백준 12993 - 이동3 (java)

 문제 : boj12993

---

 

필요 알고리즘 개념

• 정수론, 수학
  • 수학적인 사고가 약간 필요하다.
• 그리디
  
  • 태그엔 없긴한데 내 경우엔 그리디 개념으로 풀었다.

※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다.

 

---

 

풀이

  x, y 중 큰 값이 [3^a, 3^(a+1)) 일 때,
k=a 부터 0까지 감소하면서 현재 남은 x와 y중 큰 값에 3^k를 그리디하게 빼준다.
최종적으로 x와 y 모두 0이 되면 1을 출력해주고, 아니면 0을 출력해준다.. 

이 때, 3^19 = 1,162,261,467 이므로, a는 최대 18까지만 보면 된다.

 

  예를들어 예제 입력 5를 보자.

3 10

 

1. x, y중 큰 값은 10이다. [3^a, 3^(a+1))이 되려면 a는 2가 된다. (10은 9 이상이고, 27 미만이다.)

 

2. 이제 k=2부터 k=0까지 감소시키면서 빼주면 된다.

2.1 x, y 중 큰 값은 10이므로 10 - 3^2 = 1

2.2 현재  x=3, y=1 이므로, 3 - 3^1 = 0

2.3 현재 x=0, y=1 이므로, 1 - 3^0 = 0

 

3. x=0, y=0 이므로 가능한 경우라서 '1'을 출력해주면 된다.

 

 

---

 

코드 : github

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

public class Main {
    private void solution() throws Exception {
        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());
        if (a==0 && b==0) {
            System.out.println(1);
            return;
        }

        int[] pow = new int[20];
        pow[0] = 1;
        int limit = 0;
        for (int i = 1; i < pow.length; i++) {
            pow[i] = pow[i - 1] * 3;
            if (pow[i] > Math.max(a,b)) {
                limit = i-1;
                break;
            }
        }

        for (int i = limit; i >= 0; i--) {
            if (a > b) a-=pow[i];
            else b-=pow[i];
        }
        System.out.println(a==0 && b==0 ? 1 : 0);
    }
    public static void main(String[] args) throws Exception {
        new Main().solution();
    }
}