shortcoding

BOJ1067 이동

보통 다항식 곱셈이나 큰 수 곱셈같은걸 하기 위해 Convolution을 사용한다. 이 Convolution의 N^2보다 빠른 알고리즘은 다양하지만 보통 FFT나 Karatsuba같은걸 사용한다. 그런데 큰 수 곱셈을 사용해서 Convolution을 복원할 수 있지 않을까? 라는 생각을 했고, 실제로 각 자리마다 올림이 발생하지 않도록 적절히 padding을 주고 큰 수 곱셈을 계산해주니 Convolution을 구할 수 있었다. 이제 Python의 내장 빅인티져 곱셈으로 방금의 로직을 구현해주면 끝난다. 코드

BOJ13294 역팩토리얼

처음 보고 생각해낸 솔루션이 다른사람들과는 상당히 달랐던 문제다. 잘 알려진 풀이는 적당히 커진이후로는 자릿수가 각 팩토리얼마다 유일하게 대응되는걸 사용한다. 내 풀이는 k=1부터 증가시키면서 '큰 수의 자리수 덧셈 표현'=='k팩토리얼'인지 체크한다. 즉 $\sum\limits_{0\leq{}i\lt{}n}{d_i10^i}$=$\prod_{1\leq{}i\leq{}k}{i}$인 k를 구해서 출력한다. 자릿수가 너무 크니 적당히 큰 소수 mod에서 해시값만 봐주면 된다. 코드