17252 삼삼한 수

처음에는 재귀함수로 3^N <= INT_MAX N이 약 20이하로 재귀로 포함, 포함하지않음의 2^N이면 1초안에 해결할 수 있는 문제다. 따라서 3의 거듭제곱 형태의 합들을 map에 넣어서 일부분만 발췌할 수 있다

 

https://www.acmicpc.net/problem/17252

https://github.com/surinoel/boj/blob/master/17252.cpp

 

다른 사람의 코드를 보니 O(상수)로 더 쉽게 해결할 수 있었다. 그 원리를 자세히 살펴보면

 

 

https://github.com/surinoel/boj/blob/master/17252-2.cpp