ACM - Computer Transformation

링크: https://www.acmicpc.net/problem/3777

이 문제는 풀기전에 1001이 어떻게 나타나는지 n이 5이상일 경우를 직접 종이에 그려보면 규칙이 보입니다. RPG와 같은 방식으로 DFS 재귀적인 방법과 memoization을 사용하였습니다. 이 문제가 까다로웠던 이유는 n이 최대 1000이기에 2^1000은 대략 301자리 숫자이며 unsigned long long(18446744073709551615)의 숫자 범위를 훨씬 뛰어 넘는 범위이기에 직접 큰 수를 표현해야하는 사용자 정의 자료형 BigInteger class를 만들어야 했습니다. 저는 조금이라도 속도를 개선하기 위해서 n이 65일때 까지는 unsigned long long으로 계산하고 66이상부터는 직접 만든 class로 계산한 hybrid transformation을 구현하였습니다.

※ 더 최적화 할 수 있는 방법
n이 커질 때마다 1과 0의 sequence가 규칙적으로 증가하는 것으로 보인다. 이 규칙을 이용하면 재귀적인 호출 방식을 사용하지 않고 구할 수 있지 않을까?