[PS] BOJ1740 거듭제곱 ( 비트마스킹 ) with JAVA

 

 

1740번: 거듭제곱

 

 

◎ 문제풀이 

 

3의 거듭제곱의 합 중 N번째로 작은 수를 구하는 문제이다. 

 

비트마스킹을 처음 풀어본 사람이라면 발상이 어려운 문제이다. 대표적인 거듭제곱의 합은 이진수 표현식이다. 십진수를 이진수로 표현하면 2의 거듭제곱의 합으로 표현할 수 있다. 

 

10101 은 2의 0승, 2의2승, 2의 4승의 합이다. 

 

여기서 2를 3으로 바꾸어주면 3의 거듭제곱의 합으로 바꿀 수 있다. 

 

1 : 1 -> 1

2 : 10 -> 3

3 : 11 -> 3+1 = 4

4 : 100 -> 9 = 9

5 : 101 -> 9+1 = 10

 

N번째로 작은 수란 N을 이진수로 변환하고 1의 자리에 해당하는 3의 거듭제곱을 합해주면 된다. 여기서 시프트 연산을 사용하면 편리하다.  '>>' 연산으로 오른쪽으로 이진수를 하나씩 줄여나가며 1이 나올때마다 3의 거듭제곱을 합해주면 된다. 

 

이진수에 1을 & 비트연산을 해주고 1이 나오는 경우에만 3의 거듭제곱을 합해준다. 

 

10101  & 00001 = 00001 : 3을 더해준다.  ( 3 )

01010 & 00001 = 00000: 0이니 넘어간다. ( 3의 1승 )

00101 & 00001 = 00001 :  9를 더해준다. ( 3의 2승 )

00010 & 00001 = 00000 : 0이니 넘어간다. ( 3의 3승 )  

00001 & 00001 = 00001 :  81을 더해준다. ( 3의 4승 )

00000 & 00001 = 00000 :  0이니 넘어간다. 

 

결과는 3 + 9 + 81 = 93 이다.

 

◎코드

import java.io.*;
import java.util.*;

public class Main{
    
    public static void main(String[] args){
        
        Scanner sc = new Scanner(System.in);
        
        long n = Long.parseLong(sc.next());
        long threeNum = 1;
        long ans = 0;
        
        while(n > 0){
            // & 연산이 1인 경우
            if( (n&1) ==1){
                ans += threeNum;
            }
            
            threeNum *= 3; // 거듭제곱하기
            n = n>>1; // 오른쪽 시프트 연산
        }
        
        System.out.println(ans);
        
        
    }
}