백준1740번-거듭제곱(브론즈1)

문제출처 : https://www.acmicpc.net/problem/1740

1740번: 거듭제곱

문제풀이) 3의 제곱수의 합으로 이루어져 있는 경우를 생각해 봅니다.

3의 제곱수 1,3,9,27 이렇게 있는 경우를 생각해 보면 다음과 같이 생각해 볼 수가 있습니다.

27	9	3	1	숫자
0	0	0	1	1
0	0	1	0	3
0	0	1	1	4
0	1	0	0	9
0	1	0	1	10
0	1	1	0	12
0	1	1	1	13
1	0	0	0	27
1	0	0	1	28

이렇게 보면 이진수인 것을 확인 할 수 있습니다. n=4 라고 하면 이진수 4의 값이 숫자가 9 가 됩니다. 이 9를 출력해 주면 됩니다.

따라서 n의 값을 이진수로 변경 한 후에 각 자리수에 해당하는 3의 제곱수를 더해 주면 됩니다.

 

#include <iostream>

using namespace std;

int arr[100];

int Makebinary(unsigned long long num,int pos)
{
    if(num==0) return pos;
    arr[pos]=num%2;
    return Makebinary(num/2,pos+1);
}

unsigned long long mypow(int num,int b)
{
    unsigned long long res = 1;
    for(int i=1;i<=b;i++) res = res * num;
    return res;
}
int main()
{
    unsigned long long n;
    cin >> n;
    int cnt = Makebinary(n,0);
    unsigned long long res = 0;

    for(int i= 0;i<cnt;i++)
    {
        res += mypow(3,i) * arr[i];
    }

    cout << res;
    return 0;
}