문제 제목 : Numbers
문제 링크 : https://www.acmicpc.net/problem/12925

문제 제목 : n제곱 계산
문제 링크 : https://www.acmicpc.net/problem/12728

출처 : 두 문제 모두 Google > Code Jam > Google Code Jam 2008 > Round 1A C2번의 문제로 N 제한이 살짝 다를 뿐 같은 풀이로 풀리는 문제이다.

문제 이해

이 문제는 √5를 컴퓨터 상에서 정확하게 표현할 수 없기 때문에 단순히 math.pow 함수를 이용해서 풀면 오차로 인해서 값이 다르게 나오게 된다.

1차 시도

따라서 결국에는 (3 + √5) ^ N을 계산하게 되면 a + b * √5의 형식으로 나오게 된다. 이 때 a와 b를 구하고 맨 마지막에 한번만 √5를 계산해주어서 실수 오차를 피하고자 하였다.

먼저 (a1 + b1 √5) (a2 + b2 * √5)를 계산해주는 함수 cul을 만든 후

def cul(a1, b1, a2, b2):
    an = a1 * a2
    an += 5 * b1 * b2

    bn = a1 * b2 + a2 * b1

    return an, bn

N 값에 따라 a와 b를 리턴해주는 재귀함수 get를 만들었다.

get 함수는 N이 짝수일 때

get(N) = cul(get(n // 2), get(n // 2))

N이 홀수일 때

get(N) = cul(get(N - 1), get(1))

으로 계산해주었다.

def get(n: int):
    if n == 0:
        return 1, 0

    elif n == 1:
        an = 3
        bn = 1

    else:
        if n % 2 == 0:
            tan, tbn = get(n // 2)
            an = (tan ** 2) + 5 * (tbn ** 2)
            bn = 2 * tan * tbn
        else:
            tan, tbn = get((n - 1) // 2)
            ran, rbn = cul(tan, tbn, tan, tbn)
            an, bn = cul(ran, rbn, 3, 1)

    return an, bn

이런 식으로 풀었을 때

시간초과가 났고

다른 방식으로 다시 시도해보게 된다.

2차 시도

메모제이션

DP 배열을 새로 만들고 값을 저장해서 시간을 개선해보려고 하였지만 N 제한은 2×10^9이기 때문에 배열 크기 제한 때문에 실패하였다.

최종 시도

(3 - √5)을 활용

증명

주변 지인으로 부터 (3 - √5)을 활용하라는 힌트를 받아서 고민해본 결과

(3 + √5) ^ N을 a + b * √5이라고 하면
(3 - √5) ^ N는 컬레무리수이므로 a - b * √5가 된다.

우리가 구하고자 하는 값은
(3 + √5) ^ N 이고
이 값은 컬레무리수인 (3 - √5)의 N승을 더하면, (3 + √5) ^ N + (3 - √5) ^ N이 되고 이 값을 a, b로 표현하면 2a가 된다.

이 때 (3 - √5) 은 √5가 2.236... 이므로 1보다 작은 실수이고, 즉 (3 - √5) ^ N 또한 1보다 작은 실수이다.

즉 (3 + √5) ^ N의 정수부는 2a - 1이다.

점화식

(3 + √5) ^ N을 an + bn * √5이라고 하면

(3 + √5) ^ N
= (a(n-1) + b(n-1) * √5)(3 + √5)
= (3a(n−1) + 5b(n−1))+(a(n−1)+3b(n−1))√5

위와 같은 점화식이 나온다.

이 점화식에 따라 MOD 연산만 주의해서 풀면 된다.

코드

코드 : Github