개요

[링크] 백준 1629번: 곱셈

• 입력
  첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어진다. A, B, C는 모두 2,147,483,647 이하의 자연수이다.

• 출력
  첫째 줄에 A를 B번 곱한 수를 C로 나눈 나머지를 출력한다.

접근 방식

A를 B번 곱해버리면 최대 A를 21억번 곱하게 되서
무조건 시간초과가 나오는 상황이다.

따라서 재귀를 통해 B거듭제곱을 구현하려 했는데
B를 반으로 나누면서 탑 다운 방식으로 구현했다.

• 처음 발생한 문제는
  Solution함수를 재귀로 짰는 데,
  제곱을 할때 Solution * Solution으로 구현을 해서
  함수를 계속 호출해버려서 시간초과가 났다.

  그래서 long long 형의 temp 변수에 solution값을
  넣어주고 temp로 연산을 하니 시간 초과를 해결했다.

• 그다음 생긴 문제는
  edge범위의 값인 21억,21억 ,21억을 넣어줬을때
  1이 나와야하는데 다른 값이 나와서,
  어디서 문제가 발생한건지 한참 헤맸다.

  알고보니 거듭제곱B가 홀수 일때,
  return (A%C) x temp x temp % C로 구현을 했었는데
  A%C x temp x temp순으로 연산을 하다보니
  이 세 값을 먼저 연산했을때 long long범위를 벗어날 수 있어서 생긴 문제였다.
  A%C값을 맨뒤로 넣어줘서 temp x temp%C를 먼저 계산했더니 해결되었다.

코드

#include<iostream>									//

using namespace std;

void input(int& A,int& B,int& C) {					//입력받는 함수
	cin >> A >> B >> C;
}
long long Solution(int A,int B,int C) {				//재귀를 통해 계산해서 return 하는 함수

	if (B == 1) return A % C;						//제곱수가 1이면 A return

	long long temp = Solution(A, B / 2, C) % C;		//미리 temp로 Solution(A,B/2,C)%C를 정의해야 빠르다. return Solution(A,B/2,C)%C*Solution(A,B/2,C)%C
													//이런식으로 return하면 함수를 계속 호출하게되서 시간 초과난다.

	if (B % 2 == 0)									//제곱수가 짝수일땐 A^(B/2)의 제곱 연산을 재귀를 통해 하면되고
		return temp * temp % C;
	else
		return  temp * temp % C* (A % C);			//제곱수가 홀수라면 A^(B/2)의 제곱연산을 한후 A를 하나 더 곱해야한다.
													//A%C를 앞에 계산 시 A%C *temp*temp를 먼저 계산하게 된후 %C연산을 하므로
													//%C연산을 하기전에 long long범위를 넘어갈수 있다. 
}

int main() {
	int A, B, C;
	input(A,B,C);
	int ans = Solution(A,B,C)%C;
	cout << ans;
}

문풀후생

사소하지만 중요한 것들을 배우게 된 문제다.
함수를 반복호출해서 시간초과 난 것과,
나머지연산 순서를 잘 안 맞추면 범위 벗어날 수 있다는
사실들을 그동안 간과했었고 지금이라도 알게되서 다행이다.