[백준/C++] 1629 곱셈

유형	난이도	완료일	링크	특이사항
DP	실버1	23.4.6	https://www.acmicpc.net/problem/1629

 

 

오답 풀이

#include <iostream>

using namespace std;

int a, b, c;

int Recursion(int temp, int exponent)
{
	if(exponent == 2)
		return ((temp%c)*(temp%c))%c;
	else if(exponent == 1)
		return temp%c;
		
	return (Recursion(temp, exponent/2) * Recursion(temp, exponent-exponent/2)) % c;
}

int main(void)
{
	cin >> a >> b >> c;
	 
	cout << Recursion(b);
}

  시간초과로 오답처리 된 코드. 시간 안에 해결하기 위해서는 n제곱일 때의 값을 저장해두면 될 것 같은데 21억제곱까지 다뤄야하니 배열에 모든 경우의 값을 저장할 수가 없었다.

정답 코드

#include <iostream>
#include <cmath>

using namespace std;

long long int a, b, c;

long long int Recursion(int exponent)
{
	if(exponent == 2)
		return ((a%c)*(a%c))%c;
	else if(exponent == 1)
		return a % c;
	
	if(exponent%2 == 0)
	{
		long long int result = Recursion(exponent/2);
		return result * result % c;
	}
	else
	{
		long long int result = Recursion(exponent/2);
		return ((result * result) % c * (a % c) )% c;
	}
		
}

int main(void) 
{
	cin >> a >> b >> c;
	 
	cout << Recursion(b);
}

  나머지 계산 규칙을 참조하다가 해결법을 찾았다. a*b % c = ((a%c) * (b%c)) %c 라는 점을 이용해 거듭제곱의 지수를 반으로 나눠가며 수를 줄인다.(지수가 홀수인 경우에는 절반으로 나눈 값에 1승을 곱해줘야 한다.) 입력받은 N의 절반만큼씩 수를 줄이면서 1, 또는 2에 도달하면 return하기 때문에 O(logN)으로 해결할 수 있다.

연산 과정에서 계속 나머지를 이용해야하고, 최대 숫자가 21억이므로 O(log N)으로 해결해야하고 그러려면 DP적 방법을 이용해야 한다는 사고를 거치면 좋을 것 같다.