프로그래머스 - 124 나라의 숫자

프로그래머스 - 124 나라의 숫자

접근 방법 1. DP
1(1) 2(2) 4(3)
11(4) 12(5) 14(6)
21(7) 22(8) 24(9)
41(10) 42(11) 44(12)
111(13) 112(14) 114(15)
121(16) 122(17) 124(18)
141(19) 142(20) 144(21)
211(22) 212(23) 214(24)
221(25) 222(26) 224(27)
241(28) 242(29) 244(30)
411(31) 412(32) 414(33)
421(34) 422(35) 424(36)
441(37) 442(38) 444(39)
1111(40) 1112(41)

이런 식으로 숫자가 증가하기 때문에

41번째 = 1 + 14번째
14번째 = 1 + 5번째
5번째 = 1 + 2번째
이런 식으로 생각해서 DP로 풀 수 있을 것이다.
이렇게 구현을 하다가 그냥 진법변환이 가능할 것 같아서 구현을 멈췄다.

접근 방법 2. 진법변환

그냥 3진법으로 변환한다고 생각하면 $1 = 1$, $2 = 2_3$, $3 = 10_3$, $4 = 11_3$ 이런 식으로 변환 될 것이다. 3을 제외한 나머지는 모두 옳은 경우라 그냥 평범한 3진법을 구현하면 된다.(나누기, 모듈러 연산으로...)

대신 3으로 모듈러 연산을 했을 때, 0이 나오는 3, 6, 9 등의 경우에는 추가 연산이 필요하다.
$3 = 10_3$이 아니라 $3 => 4$가 되어야 하기 때문에 자리수 증가는 필요가 없고, 대신 0을 4로 표기해줘야 한다.

예를 들어, 15의 경우 기존 3진법 변환 방식으로는
15 % 3 = 0
15/3 = 5 % 3 = 2
1 % 3 = 1
이기 때문에, 120이 된다.

그러나 124나라에서는
15 % 3 = 0 => 4
(15/3 - 1) % 3 = 4 % 3 = 1
(4/3) % 3 = 1
이기 때문에, 114가 된다.

즉 모듈러 3의 결과가 0인 경우에는 나누기 3을 한 뒤 마이너스 1을 추가적으로 연산해줘서 자리수 증가를 막아주면 된다.

코드는 다음과 같다.

#include <string>
#include <vector>

using namespace std;

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