백준 및 코드포스

1, 2, 4로만 이루어진 3진수 체계로 주어진 n을 나타내면 되는 문제입니다.

어떻게 해결해야 할까 고민 많이 했는데, 노트에 적어보면서 규칙을 찾을 수 있었습니다.

거꾸로 생각했을 때,

answer = "124" 인 경우

$n = 18$일 때 answer = "124" 임을 도출할 수 있었고,

1. n % 3 이 각각 0, 1, 2일 때 뒷자리가 4, 1, 2 임을 알 수 있었습니다.

그다음 규칙을 찾는 것이 어려웠는데,

$n = \frac{(n - 1)}{3}$

2. 위와 같이 적용했을 때, 1번이 다시 적용됨을 알 수 있었습니다.

위와 같이 문자열을 만들어주면 거꾸로 저장이 되니까,

return 전에 완성된 문자열을 뒤집어주면 정답입니다.

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

string solution(int n) {
    string answer = "";
    while(n) {
        int tem = n % 3;
        if(tem == 1) answer += "1";
        else if(tem == 2) answer += "2";
        else if(tem == 0) answer += "4";

        n = (n - 1) / 3;
    }
    reverse(answer.begin(), answer.end());
    return answer;
}

보잘것없는 문제 정답 도출까지의 제 필기입니다.