백준 1740번 거듭제곱 JAVA 구현해보기

---

```

백준 1740번 거듭제곱 JAVA 구현해보기

```

이번 글을 통해 배워갈 내용

1. 백준 1740번 거듭제곱 풀이

---

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

1740번: 거듭제곱

 

백준 1740번 거듭제곱은

난이도 실버 등급의 문제로서

 

서로 다른 3의 제곱을 가지고 만들 수 있는 숫자 중에 N번째로 작은 숫자를 구하면 되는 문제입니다.

이때 N은 500000000000 이하의 자연수입니다.

 

예를 들어

 

1

3   4

9  10  12  13

27  28  30  31 36 36 37 39 40

...

으로 나아가면

좌측상단에서부터 첫 번째 두 번째 세 번째 이렇게 N번째 까지 세어나가면 됩니다.

 

---

30분 정도 위에 링크를 방문하셔서 풀어보시고

안 풀리시는 경우에만 아래 해답을 봐주시면 감사하겠습니다.

---

 

수학적으로

위에 수가 나열된 것을 자세히 보면

 

1은 1개

3은 2개

9는 4개

27은 8개의 숫자로서

2의 제곱으로 증가한다는 것을 알수있습니다.

 

그림으로 보시면 다음과 같습니다.

 

 

 

위에 그림처럼

N번째 숫자를 계속 빼주고

뺀 숫자만큼 결괏값에 3의 제곱을 해서 더해주면 됩니다.

 

주의할 점은

 

500000000000번째 N의 결괏값이

1968190469967719331인데

이는 더블로 할 경우 초과가 되기 때문에

기본 제공되는 Math.pow 보다는

직접 만든 제곱 함수를 사용해주어야 합니다.

 

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


public class Main {

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

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

        Long inputNum = Long.parseLong(br.readLine());

        Long outputNum = 0L;
        while (inputNum > 0L) {
            Long tempCnt = 0L;
            Long num = 1L;
            while (inputNum >= num * 2L) {
                num *= 2L;
                tempCnt++;
            }
            inputNum -= num;
            outputNum += myPowBy3(tempCnt);
        }
        System.out.println(outputNum);
    }

    private static Long myPowBy3(Long tempCnt) {
        Long retVal = 1L;
        for (int i=0;i<tempCnt;i++){
            retVal *= 3;
        }
        return retVal;
    }
}

 

읽어주셔서 감사합니다

 

무엇인가 얻어가셨기를 바라며

 

오늘도 즐거운 코딩 하시길 바랍니다 ~ :)

 

---