[백준] 1740 거듭제곱

4540 단어 psps

문제

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

알고리즘

수학

풀이

수학에서 2진수를 10진수로 바꾸는 것과 동일하다.
먼저 10을 2진수로 바꾸면 1010이 된다.
여기서 2의 1제곱과 2의 3제곱을 더한 값은 10이 된다는 것을 알 수 있다.

[결과]
1. 숫자 N을 2진수로 변환한다.
2. 여기서 10진수로 바꾸려면 각 자릿수에서 1인 값을 2의 각 자릿수 제곱값을 구하여 다 더해준다.
3. 3의 거듭제곱 중에서 N번째 작은 수는 숫자 N을 이진수로 바꾸고 그 이진수에서 자릿수가 1인 것을 3의 각 자릿수 제곱값을 더한 값이 된다.
4. 이유는 문제에서 3의 제곱으로 더한 숫자중 N번째 숫자라고 명시해줬기 때문이다.

코드

public long solution(long x) {
        long answer = 0L;
        StringBuilder binary = new StringBuilder();

        while (x > 1) {
            binary.append(x % 2);
            x = x / 2;
        }

        binary.append(x);

        for (int i = 0; i < binary.length(); i++) {
            long temp = 1;
            if (binary.charAt(i) == '1') {
                for (int j = 0; j < i; j++) {
                    temp *= 3;
                }
                answer += temp;
            }
        }

        return answer;
    }

좋은 웹페이지 즐겨찾기