[소프티어/Softeer] 수퍼바이러스 c++

수퍼바이러스 문제 링크 

 

리뷰 

바이러스가 처음에 K마리 있고, N초 동안 증가율 P배씩 증가한다. 

주어진 증가율 P배는 0.1초당 증가율이고, 제한 시간 N초는 1초 단위다. 이 단위 차이를 반영하자. 

 

0.1초당 P배씩 증가하니까 1초당 바이러스는 10 * P배씩 증가한다.  

증가율 P가 아니라 주어진 N초에 10을 곱해줘도 된다.

N초 동안 P배씩(0.1초당) 증가하므로,  10 * N초 동안 P배씩 증가하는 것과 같다. 

 

N초는 long long 자료형이니까 매우 큰 숫자가 주어진다. 

따라서 분할정복 함수 cal() 을 구현한다. 

 

몇 제곱인지를 구하는 것이니까 몇승을 하는지 재귀호출로 구할 수 있다. 

1승이면 p배를 리턴한다. 

ll cal(ll cnt){ // cnt 초 동안  x배
  if(cnt == 1) return p;

2승이면 1승 * 1승을 재귀호출해서 구한 값으로 리턴한다. 

  ll result = cal(cnt/2);

  result = result * result % MOD; // 짝수 승

홀수 승이면, /2 승 * /2 승 * 1승 해주면 된다. 

ex) 5승 ==> 2승 * 2승 * 1승 

if(cnt % 2 == 1) result = (result * p) % MOD; // 홀수 승은 p를 한번 더 곱한다.

 

답을 10000007로 나눈 나머지를 리턴해야 하니까 곱할 때 마다 MOD로 나눈 나머지를 저장하자. 

 

맞았습니다 코드 

#include<iostream>
#define MOD 1000000007
#define ll long long
using namespace std;

ll k, p, n;

ll cal(ll cnt){ // cnt 초 동안  x배
  if(cnt == 1) return p;
  ll result = cal(cnt/2);

  result = result * result % MOD; // 짝수 승
  if(cnt % 2 == 1) result = (result * p) % MOD; // 홀수 승은 p를 한번 더 곱한다.
  return result;
}
int main(void) {
  ios::sync_with_stdio(0);
  cin.tie(0);

  cin >> k >> p >> n;

  // 0.1초 마다 p배 -> 1초마다 p*10배 -> 10*N초 동안 p배
  ll answer = (cal(10 * n) * k) % MOD;
  cout << answer;
  return 0;
}

 

제출기록