Softeer Lv2. 바이러스

Softeer.ai의 Lv.2 바이러스 문제

엄청나게 큰 자료형을 다루는 문제

숫자가 큰 값을 사용할 때, 결과값을 어떤 수로 나누라고 하는 경우

모든 계산을 끝내고 나머지를 나누면 시간초과가 발생함

이 경우, 연산하는 과정에서 계속 나머지를 나누어 주면 된다

https://softeer.ai/practice/6284

1. 문제

---

간단 설명

바이러스가 숙주의 몸속에서 1초당 P배씩 증가한다.

처음에 바이러스 K마리가 있었다면 N초 후에는 총 몇 마리의 바이러스로 불어날까? N초 동안 죽는 바이러스는 없다고 가정한다.

1 ≤ K ≤ 108인 정수

1 ≤ P ≤ 108인 정수

1 ≤ N ≤ 106인 정수

가 주어질 때,

최종 바이러스 개수를 1000000007로 나눈 나머지를 출력하는 문제

2. 문제 분석

---

필요변수

바이러스 수 K, 증가율 P, 총 시간 N이 주어짐

바이러스의 수는 1초마다 P배 증가하므로

K = K * (P)^N 이 된다

K, P, N이 모두 최대값인 경우 2^6보다 크고, 2^7보다는 작다고 생각해보면

K = 2^6 * (2^6)^(2^6)이 된다

K = 약 2^390 정도 되기 때문에 int형으로는 처리 불가능. 혹은 계산하는 과정에서 이를 처리하는 과정이 필요함

int 자료형은 -2^31 ~ 2^31 (64bit 기준)까지 다룰 수 있기 때문에 오버플로우가 날 수 있으므로

long long int형을 사용함

long long int K

알고리즘

1. K, P, N을 입력받고
2. N번 2~3번 과정을 반복한다
3. (K * P) : 바이러스 K가 P배 증식한다
4. 3에서 계산한 (K * P)를 1000000007로 나머지 연산을 한다
5. K를 출력한다

• 모두 계산하고 모듈러 연산을 수행하는 것과, (K * P)^N % MOD

  한번 계산을 할 때마다 모듈러 연산을 수행하는게 결과값이 같을까? (K * P % MOD)^N

• 이를 적용하기 위해서는 모듈러 연산의 분배법칙에 대해 알아야함

    (A + B) % p = ((A % p) + (B % p)) % p
    (A * B) % p = ((A % p) * (B % p)) % p
    (A - B) % p = ((A % p) - (B % p) + p) % p
  

• 모듈러 연산은 곱셈에 대해 분배법칙이 성립하므로, 제곱도 문제없음

• EX) k=2, p=2, n=5고, 10으로 모듈러 연산을 한다고 가정하면

  1) 전체 계산 후 모듈러 연산은 4, 8, 16, 32, 64이므로 결과는 4가 된다 2) 한번 계산할때마다 모듈러 연산을 수행하면 4, 8, 6(16%10), 2(12%10), 4 이므로 같음

3. 소스코드

---

#include<iostream>

using namespace std;

int main(int argc, char** argv)
{
  int mod = 1000000007;
  int P, N;
  long long int K;

  cin >> K >> P >> N;
  
  // (K * P % MOD)^N
  while(N--){
    K = (K*P)%mod;
  }

  cout << K;
  
   return 0;
}