Programmers 12899 124 나라의 숫자

02 Jan 2021 in Algorithm

문제 링크 : https://programmers.co.kr/learn/courses/30/lessons/12899

나의 풀이

10진법	3*3	3	1	124나라
1 = 1	0	0	1	1
2 = 2	0	0	2	2
3 = 3	0	0	3	4
4 = 3 * 1 + 1	0	1	1	11
5 = 3 * 1 + 2	0	1	2	12
6 = 3 * 1 + 3	0	1	3	14
7 = 3 * 2 + 1	0	2	1	21
8 = 3 * 2 + 2	0	2	2	22
9 = 3 * 2 + 3	0	2	3	24
10 = 3 * 3 + 1	0	3	1	41
11 = 3 * 3 + 2	0	3	2	42
12 = 3 * 3 + 3	0	3	3	44
13 = 3 * 3 * 1 + 3 * 1 + 1	1	1	1	111
14 = 3 * 3 * 1 + 3 * 1 + 2	1	1	2	112
15 = 3 * 3 * 1 + 3 * 1 + 3	1	1	3	114

<!–

임의의 자연수 num은

\(num = 3^n \times k_n + 3^{n-1} \times k_{n-1} .... 1 \times k_0\) 로 구성되며 각각의 \(k_n, k_{n-1} .... k_0\) 의 값 중 3을 4로 바꿔준다면 124 나라의 각 자리수와 모두 일치한다는 것을 알 수 있다.

이 때 k_0의 값은 num%3의 값에서 num%3이 0일때만 3으로 생각하면 된다.

이렇게 계산한 k_0의 값을 위 식에 대입한다. \[newnum= num - k_0 = 3^n \times k_n + 3^{n-1} \times k_{n-1} .... 3 \times k_1\]

양 변을 3으로 나눠주면 처음 식과 동일하다는 것을 알 수 있다. k_0의 값을 구할 때와 동일한 방법으로 k_1의 값을 구할 수 있다. 이 과정을 반복하여 수행하면 k_2 … k_n의 값을 모두 구할 수 있다. \[newnum \div 3 = 3^{n-1} \times k_n + 3^{n-2} \times k_{n-1} .... 1 \times k_1 = 3^m \times k_m + 3^{m-1} \times k_{m-1} .... 1 \times k_0\]

( \(newnum\) 의 값은 반드시 3으로 나누어 떨어지기 때문에 \(newnum \div 3\) 또한 자연수임을 알 수 있다.) –>

풀이 코드 : 12899 124나라의 숫자

#include <string>
#include <vector>
#include <cmath>


using namespace std;

string solution(int n) {
    string answer = "";
    int last; 
    while(n!=0){
        last = n%3;
        if(last == 0) last = 3;
        n -= last;
        if(last == 3) last = 4;
        answer = to_string(last) + answer;
        n/=3;
    }
    return answer;
}

채점결과