[softeer] 소프티어(파이썬): 수퍼바이러스 ★★★

문제

Softeer

- 수퍼바이러스는 0.1초당 P배씩 증가한다.

- K마리가 있었다면 N초 후에는 총 몇 마리의 수퍼바이러스로 불어나는지를 구하는 문제이다.

- N초 동안 죽는 수퍼바이러스는 없다.

- 수퍼바이러스는 일반 바이러스보다 훨씬 오래 생존할 수 있어 N이 매우 클 수 있다.

- 바이러스의 수가 K일때 1 ≤ K ≤ 10^8인 정수이다.

- 증가율이 P일때 1 ≤ P ≤ 10^8인 정수이다.

- 총 시간이 N일때 1 ≤ N ≤ 10^16인 정수이다.

- 최종 바이러스 개수를 1000000007로 나눈 나머지를 출력한다.

알고리즘

위 문제를 해석해보면 K * P^10N을 구하는 문제인 것을 확인할 수 있다. 그러나 시간 복잡도가 O(N)인 for문 하나로 K * P^10N을 풀게 되면 시간 초과가 나오게 된다. 그 이유는 총 시간 N의 범위가 10^16까지이기 때문이다. 시간 초과를 안 하기 위해서는 O(log N) 시간 복잡도를 갖는 재귀 함수를 통해 풀어야 한다. 

- 함수를 만들고 함수는 증가율과 총 시간을 10배 한 값을 받아야 한다.(0.1초당 P배씩 증가하기 때문이다.)

- 함수는 P^10N에서 P의 지수인 10N을 재귀적으로 나눠준다.

- 바이러스의 수, 증가율, 총 시간을 입력받는다.

- 0.1초당 P배씩 증가하기 때문에 N을 10배 해준다.

- 재귀 함수에서 출력된 값을 처음 바이러스의 수와 곱해준다.

- 총 바이러스는 1000000007로 나누고 나눈 나머지를 출력한다.

- 다음 사진을 보면서 이번 문제에 재귀 함수를 쉽게 이해할 수 있도록 해보자.

<사진>

코드

import sys


# 지수를 재귀적으로 나눈다.
def f(x, y):
    if y == 1:
        return x

    elif y % 2 == 0:
        a = f(x, y / 2)
        return a * a % 1000000007

    else:
        b = f(x, (y - 1) / 2)
        return b * b * x % 1000000007


k, p, n = list(map(int, sys.stdin.readline().split()))
# 0.1초당 p배씩 증가이기 때문에 계산을 편리하게 하기위해 n을 10배 해준다.
n = 10 * n
result = f(p, n)
result *= k
print(result % 1000000007)

결과

위 코드에서 함수 안에 print(x, y)를 작성하면 재귀 함수가 위 사진과 같이 진행되는 것을 확인할 수 있다.

<출력화면>

따라서 코드를 분석하게 되면 함수를 하나 만들어 함수를 통해 지수를 재귀적으로 나누는 것이다. 이때, 지수가 1이 되면 P^1 이기 때문에 P값을 리턴하고 지수가 짝수이면 지수를 2로 나누어 함수에 다시 넣고 다시 넣은 함수를 변수에 넣어 곱하기하여 리턴하는 것이다.(이러한 과정이 재귀적으로 함수를 만든 것이다.) 또, 지수가 홀수이면 지수를 - 1 해주고 그 값을 2로 나누어 함수에 다시 넣고 다시 넣은 함수를 변수에 넣어한번 곱한 후 P를 곱해 리턴하는 것이다. 마지막으로 함수에서 출력된 값을 바이러스 수와 곱하고 1000000007로 나눈 나머지 값으로 출력한다.

github

junjange/CodingTest