문제

문제 링크

코드

def solution(n):
    answer = []
    while n >= 3:
        if n % 3 == 0:
            answer.append('3')
            n = n//3 - 1
        else:
            answer.append(str(n%3))
            n = n//3
    if n != 0:
        answer.append(str(n))
    tanswer = []
    for i in answer:
        if i == '3':
            tanswer.append("4")
            continue
        tanswer.append(i)
    tanswer.reverse()
    answer = ''.join(tanswer)
    return answer

접근 방법

1. 순열적인 접근으로 규칙을 찾아보았다.
2. 그러나 자연수 n -> a_n 의 관계는 찾기 어려울 듯 했다.
3. 오히려 정수론적인 접근인 진법과 관계 있으리라 생각했다.
4. 왜냐하면 같은 수이지만 표기법이 다른 것이 바로 진법이기 때문이다.
5. 대충 보았을 땐 3진법스러웠다. 그러나 4라는 숫자 때문에 규칙을 찾기 어려웠다.
6. 그래서 그냥 4를 3으로 바꿔서 규칙을 찾아보았다. (규칙을 찾기 쉽게 변형)
7. 그렇게 보니 3진법이 맞았다. 그러나 특이한 규칙이 또 하나 존재했다.
8. 바로 0이 없는 3진법이었다.
9. 결론적으로 0이 없는 3진법으로 수를 표현하고 3을 4로 바꿔주기만 하면 되는 문제라고 결론지었다.
10. 그래서 위와 같은 규칙을 그대로 코드로 구현하여 문제를 풀었다.

정리 (문제 접근 방식)

1. 알고리즘이 떠오른다. -> 바로 적용
2. 알고리즘이 떠오르지 않는다.
   a. 규칙을 찾기 위해 귀납적 추론을 위한 관찰 시작
   b. 작은 스케일에서 순열적인 접근으로 귀납 추론을 시도해본다.
   c. 순열 == f:N->N, n->an
   d. 순열적인 접근으로 규칙을 못 찾겠다면 정수론적인 접근을 시도한다.
   e. 정수론적인 접근은 함축적인 수학 공식을 찾아내거나 정수론 공식을 찾아낼 수 있어야 한다.
3. 논리적으로는 맞는 코드이나 시간 초과가 날 때
   a. 시간 초과가 난다는 것은 최적화가 필요함을 뜻한다.
   b. 먼저 적절한 자료구조를 사용했는지 검토한다.
   c. dp를 적용할 수 있는지 검토한다. (분할정복이 가능한지 검토)
   d. dp는 점화식(캐시)을 찾거나, 배열(이동)을 이용해서 구현할 수 있다.