[코딩 테스트] 소프티어(Softeer) 연습 문제 - 바이러스

코딩 테스트를 위한 소프티어(Softeer) 연습 문제 중 바이러스 문제를 풀어보았다.

 

연습 문제 - 바이러스

• 난이도 : level 2
• 정답률 : 30%

https://softeer.ai/practice/info.do?idx=1&eid=362 

Softeer

 

문제 해설

최초 K개의 바이러스가 초당 일정 배수 P로 증가하는데 N초 후에는 바이러스가 몇 개가 되는지에 대한 문제이다. 죽는 바이러스는 없으니 별로 어렵지 않은 문제이다. K, P가 10^8이고 N이 10^6이다. 여기서 주의할 점은 바이러스 개수를 1000000007으로 나눈 나머지로 표시하는 것이다. 단순히 mod 연산을 하면 되는데 괜히 어렵게 생각하다 보면 오히려 복잡해질 수 있다. 하나는 단순이 for loop로 구현해 보았고 하나는 재귀함수를 통해 구현해 보았다.

 

코드 1

#include<iostream>

using namespace std;
#define mod 1000000007
typedef unsigned long long ull;

int main(int argc, char** argv)
{
	ull K, P, N;
	cin >> K >> P >> N;

	int k = K;
	for (int i = 0; i < N; i++) {
		k = k * P % mod;
	}
	cout << k << endl;
	return 0;
}

 

코드 2

#include<iostream>
using namespace std;
#define mod 1000000007
typedef unsigned long long ull;
ull increase(ull k, ull p, int n) {
	if (n <= 0) return k;
	increase(k * p % mod, p, n - 1);
}
int main(int argc, char** argv)
{
	ull K, P, N;
	cin >> K >> P >> N;
	ull res = increase(K, P, N);
	cout << res << endl;
	return 0;
}

 

결론

처음에 재귀함수 방식으로 구현하였는데 답이 틀리거나 시간이 오래 걸리는 문제들이 발생했다. 아무래도 stack을 많이 사용하거나 mod 연산을 불필요하게 사용하다 보니 문제가 발생하였다. 또한 재귀함수는 혹시나 해서 unsinged long long을 사용했는데 굳이 필요 없긴 하지만 문제의 숫자가 커지거나 실수를 예방하기 위해 사용하는 것도 나쁘지 않은 것 같다.