124나라의 숫자(Level2)

• 문제 링크: 코딩테스트 연습 > 연습문제 > 124나라의 숫자

• 문제 이해

  1. 우리가 사용하는 10진법을 124나라에 맞게 바꿉니다.
  2. 일반적으로 10진법은 0부터 시작하지만, 독특하게 여기서는 1부터 시작합니다.

• 알고리즘 구현

  1. 먼저, 1-2-3-4일 때, 1-2-4-11인 것을 보면, 3개의 수가 지나면 자릿수가
     증가함을 파악합니다.
  2. 이는, 0-1-2-3일 때, 0-1-2-10인 3진법의 형태와 같다는 것을 알 수 있습니다.
  3. 진법처리시 몫과 나머지로 나누어 처리하는 것이 중요한데, 몫은 다음 깊이에서 다시
     처리하고, 현재 깊이에서는 나머지를 답에 붙이는 방식으로 사용합니다.
     (손으로 직접 3진수의 형태를 나타내보면 편리합니다.)
  4. 추가로, 해당 문제에서는 수가 1부터 시작하므로, 재귀에 넣을 때나, 나머지의 형태를
     BASE124에서 찾을 때 1을 빼줍니다.

• 알고리즘

#include <string>
#include <vector>

using namespace std;

const string BASE124 = "124";

void convertNum(int n, string &answer, bool first_zero) {
    string ret;
    if (n == 0) 
    {
        if (first_zero)
            answer = "1";
    	return ;
    }
    convertNum((n - 1) / 3, answer, 0);
    answer += BASE124[((n - 1) % 3)];
}

string solution(int n) {
    string answer = "";
    convertNum(n, answer, 1);
    return answer;
}