programmers [C++] : 124 나라의 숫자

programmers.co.kr/learn/courses/30/lessons/12899#

코딩테스트 연습 - 124 나라의 숫자

문제 설명

---

124 나라가 있습니다. 124 나라에서는 10진법이 아닌 다음과 같은 자신들만의 규칙으로 수를 표현합니다.

RULE

1.  124 나라에는 자연수만 존재합니다.

2. 124 나라에는 모든 수를 표현할 때 1, 2, 4만 사용합니다.

예를 들어서 124 나라에서 사용하는 숫자는 다음과 같이 변환됩니다.

 

 

접근 방법

---

저는 DP로 접근을 했습니다 1,2,4로 나누어지는 것 뿐 본질적으로 3진법으로 볼 수 있다고 생각 했습니다. 

그래서 3으로 나누었을때 나머지가 0이면 나머지가 마지막 숫자인 4가 되고 앞의 숫자는 몫에서 -1을 하고 몫을 앞의 과정을 반복해서 시행합니다. 

 

코드

---

#include <string>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;

string answer = "";
void dp(int n){
    int mauk = n/3;
    int res = n%3;
    if(res==0){
        res=4;mauk-=1;
    }
    answer+=to_string(res);
    if(mauk<3) {
        if(mauk==0)return;
        answer+=to_string(mauk);return;
    }
    else if(mauk==3){
        mauk=4;answer+=to_string(mauk);
        return;
    }
    else{dp(mauk);}
}
string solution(int n) {
    
    dp(n);
    reverse(answer.begin(),answer.end());
    return answer;
}

funny algorithm 0_<