[BOJ1740] 거듭제곱 (Java)

BOJ1740 거듭제곱

문제풀이

정말 신기한 문제 비트연산자와 이진법을 활용하는 방법을 알아둘 필요가 있다고 느꼈다. 핵심은 3의 제곱수를 하나씩만 사용할 수 있다. 라는 조건이다.

몇번째인지를 나타내는 숫자 N을 이진수로 바꾸면 다음과 같다.

• 2 -> 10(2), 3 -> 11(2), 4 -> 100(2)

이 때 각 자릿수가 2의 제곱수를 나타내지만 3의 제곱수로 생각하는 것이다. 따라서 다음과 같다.

• 2 -> 10(2) -> 3^1
• 3 -> 11(2) -> 3^1 + 3^0
• 4 -> 100(2) -> 3^2

비트연산자를 이용하면 별도의 2진수 변환 과정을 거치지 않아도 되며 빠르게 확인할 수 있다.

• N이 0이 될 때 까지 다음을 진행한다.
• 먼저 N & 1 연산을 통해 N의 이진수의 가장 오른쪽 비트가 켜져있는지(1인지) 확인한다.
  • 1이라면 승수를 나타내는 count만큼 제곱하여 answer에 더 한다.
  • Math 라이브러리의 pow를 사용하지 않은 것은 pow가 double형을 리턴하기 때문에 불완전하기 때문이다. 따라서 별도의 power 매서드를 만들었다.
• 승수 count를 증가시키고 N을 오른쪽 쉬프트 1 한다.

구현코드

import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		long N = sc.nextLong();
		long answer = 0;
                int count = 0;

                while (N > 0) {
                    if ((N & 1) == 1) {
                        answer += power(3, count);
                    }
                    count++;
                    N = (N >> 1);
                }

                System.out.println(answer);
	}
	
	private static long power(long a, long b) {
		if(b == 0) return 1;
		if(b == 1) return a;
		
		long temp = power(a, b / 2);
		
		if(b % 2 == 0) {
			return (temp * temp);
		} else {
			return ((temp * temp) * a);
		}
	}
}