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

이번 글을 통해 배워갈 내용
- 백준 1740번 거듭제곱 풀이
https://www.acmicpc.net/problem/1740
1740번: 거듭제곱
3의 제곱수를 생각하자. 3의 0제곱, 3의 1제곱, 3의 2제곱, ... 은 순서대로 1, 3, 9, 27, ... 이 된다. 이를 바탕으로, 한 개 이상의 서로 다른 3의 제곱수의 합으로 표현되는 수를 생각할 수 있다. 예를
www.acmicpc.net
백준 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;
}
}
읽어주셔서 감사합니다
무엇인가 얻어가셨기를 바라며
오늘도 즐거운 코딩 하시길 바랍니다 ~ :)
'Java > Java 알고리즘' 카테고리의 다른 글
| 백준 10212번 Mystery JAVA 구현해보기 (2) | 2021.12.05 |
|---|---|
| 백준 2530번 인공지능 시계 JAVA 구현해보기 (0) | 2021.12.05 |
| 백준 2161번 카드1 JAVA 구현해보기 (0) | 2021.12.03 |
| 백준 20001번 고무오리 디버깅 JAVA 구현해보기 (0) | 2021.12.03 |
| 백준 16435번 스네이크버드 JAVA 구현해보기 (0) | 2021.12.01 |