BOJ 7765 : Supersquare

문제 링크 : http://acmicpc.net/problem/7765

 

500이하의 자연수 N을 입력받으면, 2N 자리 제곱수를 출력하면 된다.

단, 앞 N자리와 뒤 N자리 또한 제곱수여야 한다.

 

지금 내가 서술하는 풀이가 정해라면 그리 좋은 문제 같진 않다...

Naive 하게 코드를 돌려보면서 규칙을 찾아봤는데 꽤 오래걸렸다.

규칙 찾고 정리하는데 3일 정도 걸렸다. 3일 내내 잡고 있었던 건 아니지만 꽤 어려웠던 건 확실.

 

N이 짝수일 때 (N = 2n + 2 형태)

( 5 * 10⁽²ⁿ⁺¹⁾ - 10⁽ⁿ⁺¹⁾ + 1 )² 를 전개하면 앞 (2n+2) 자리는 (5 * 10ⁿ - 1)² 이고 뒤 (2n+2) 자리는 (10⁽ⁿ⁺¹⁾ - 1)² 이다.

이걸 한번에 발견한 것은 아니고 물론 Naive 하게 돌려보면서 찾은 규칙이다.

단, 답이 최대 1000자리 수까지 가기 때문에 직접 제곱하면 안되고 규칙을 찾으면 된다.

N = 2일때는 그냥 1681 이 되고,

N > 2일때는 2 4 9 0 1 9 8 0 1 형태고 각 숫자의 개수가 N에 관한 식으로 주어진다. (찾기 쉬움)

 

N이 홀수일 때

이게 진짜 귀찮았다. Naive 하게 돌려가며 공통된 규칙이 없나 찾아본 끝에 나온 결론이다.

N = 5 이면 24964 01296 인데, 1296 = 36² 이고,  24964 + 36 = 25000 이다.

N = 7 이면 2499561  0192721 인데, 192721 = 439² 이고, 2499561 + 439 = 2500000 이다.

N = 9 이면 249987721  150773841 인데, 150773841 = 12249² 이고, 249987721 + 12249 = 250000000 이다.

 

이렇게 놓고 보면 규칙 찾기가 쉬워 보이지만, 아래 그림처럼 N이 7만 돼도 Supersquare 가 굉장히 많다.

여기서 2499561 0192721 을 딱 정해서 규칙을 찾을 생각을 하기가 나는 쉽지 않았다.

N = 7 일때 Supersquare

 

위에서 찾은 규칙대로 식을 짜고 삽질을 조금 하다 보면,

N - Supersquare 의 앞 N자리는 곧 (1 / 루트 40) 의 소수점 아래 처음 (N + 1) / 2 자리 라는 것을 알게 된다.

 

OEIS 의 힘을 빌리면, (1 / 루트 40) = 1, 5, 8, 1, 1, 3, 8, 8, ... 이다.

실제로 위 예제들로 해보면, N = 9 인 경우 249987721 = 15811² 이고 이는 소수점 아래 처음 5 자리와 같다.

 

이제서야 구현의 가닥이 잡히기 시작한다.

OEIS 에서 (1 / 루트 40) 의 처음 250 자리를 가져와 배열에 넣고,

큰 수 연산을 해주면 된다. 긴자리 수 곱셈, 뺄셈을 가볍게 구현해주면 100점을 받을 수 있다.

 

푼 사람 1명이고 문제가 재밌어보여서 뛰어들었다가 고생만 엄청 했다...