[백준] 1629 번 : 곱셈 / C++

[문제]

문제 :

 자연수 A를 B번 곱한 수를 알고 싶다. 단 구하려는 수가 매우 커질 수 있으므로 이를 C로 나눈 나머지를 구하는 프로그램을 작성하시오.

 

입력 : 

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

 

출력 :

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

 

[코드 풀이]

[실패한 코딩]

첫 번 째 시도.

 분할 정복을 사용하지 않고 for문을 이용해서 시도하였다.

계속 제출할 때마다 실패, 시간 초과가 떠서 코드가 점점 복잡해지기 시작했고 포기한 시점에서의 마지막 코드이다.

 

 모든 경우의 수를 다 따져서 조건문을 이용하다 보니 복잡해졌고, 반복문을 이용한 시간복잡도 때문에 시간초과를 해결할 수 없어서 포기하게 됐다.

#include <bits/stdc++.h>
using namespace std;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	long long int target_number;
	int count;
	int modu;
	long long int sol=1;
	
	long long int end = 0;
	long long int finder = -1;

	cin >> target_number >> count >> modu;
	
	vector<int> vecky;
	if (count == 1) {
		cout << target_number % modu;
		return 0;
	}
	for (int i = 0; i < count; i++) {
		if (finder != -1) {
			break;
		}
		else {
			sol = (sol * (target_number% modu))%modu;
			vecky.push_back(sol);
			
			for (int j = 0; j < i; j++) {
				if (vecky[i] == vecky[j]) {
					finder = j;
					break;
				}
			}
			end = i;
		}
	}
	if (finder == -1) {
		cout << vecky[count-1];
	}
	else {
		int recount = (count - finder) % (end - finder) - 1;
		if (recount == -1) {
			recount = end - 1;
			cout << vecky[recount];
		}
		else {
			recount += finder;
			cout << vecky[recount];
		}
	}
	return 0;
}

 그 다음은 

 이번엔 분할 정복의 개념을 조금 도입했다. 제곱의 수를 짝수일 때, 홀수일 때를 구분짓고, for문의 연산을 반으로 줄일 수 있도록 하였다. 하지만 그래도 여전히 시간복잡도는 여전하여 시간초과로 실패했다...

 그래도 재귀함수를 어떻게 짜야하는지 눈에 보인다!

#include <bits/stdc++.h>
using namespace std;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	long long int target_number;
	int count;
	int modu;
	long long int sol=1;
	
	cin >> target_number >> count >> modu;

	if (count % 2 == 0) {
		for (int i = 0; i < (count / 2); i++) {
			sol = (target_number * sol)%modu;
		}
		//sol = sol % modu;
		sol = (sol * sol) % modu;
	}
	else {
		for (int i = 0; i < (count / 2); i++) {
			sol = (target_number * sol)%modu;
		}
		//sol = sol % modu;
		sol = (((sol * sol) % modu)*target_number)%modu;

	}
	cout << sol;

	return 0;
}

 

 

[성공한 코딩]

분할 정복을 이용하여 거듭제곱 연산을 풀이하도록 하였다.

드디어 성공했다!!!

 

여기까지 오는데 과정은,

• 재귀함수의 return 부분에서 재귀함수를 2개씩 사용하게 되어서 시간초과.
• 홀수 부분의 출력값을 받을 때 값 연산의 순서가 틀려서 수학적으로 오류.

 여기서 시간초과는 재귀함수를 호출할 때 한 번만 호출하도록 tmp 변수를 설정해서 해결했고,

 수학적 오류는 조금 찾기 어려웠다. 입/출력 예제를 몇 개 더 찾아서 했을 때 계속 정답이 나와서 내가 쓴 공식이 틀렸을 거라고 생각을 못 했다. 어쨌든 찾아서 해결!!

#include <bits/stdc++.h>
using namespace std;

long long int func(int x, int y, int z) {
	//x는 피거듭제곱수, y는 제곱하는 횟수, z는 나누는 값.
	if (y == 1) {
		return x % z;
	}
	long long int tmp = func(x, y / 2, z);
	if (y % 2 == 0) {
		return tmp * tmp % z;
	}
	else {
		return (x *(tmp * tmp % z))%z;
	}
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int target_number;
	int count;
	int modu;
	long long int sol;

	cin >> target_number >> count >> modu;

	sol = func(target_number, count, modu);

	cout << sol << '\n';

	return 0;
}

main함수는 입,출력이 전부이고, func 함수에서 문제에서 원하는 풀이가 다 있다.

 func 함수의 기능은 거듭제곱을 한 큰 수의 나머지를 구할 때,
거듭제곱 연산이나, 나머지 연산을 하는 연산이 너무 오래 걸리지 않아야 한다.

 

 또한 입력으로 받는 피거듭곱셈수, 거듭곱셈의 횟수, 나누는 수가 큰 수까지 포함하기 때문에 단순한 거듭제곱의 연산 문제가 큰 문제로 변할 수 있어서, 분할정복을 사용한다. (사실 문제 카테고리에 써 있는 '분할정복'이라는 말이 있어서 발상할 수 있었다~)

 

분할 정복은 거듭제곱의 특성 및 나머지 연산할 때의 특성을 이용하여 큰 것을 작은 것 여러 개로 쪼갤 수 있었고, 이 과정에서 재귀함수를 사용하였다.

 

//나머지 연산과 거듭제곱의 특성은 아이패드에 열심히 써놓은게 있어서 조금 잤다가 일어나서 다시 써야겠다.

 

 열심히 하나 하나 써서 경험적으로 확인해서 코드에 적용하고, 이후에 수학적 오류 찾을 때 검색해서 나머지 연산의 특성에 대해서 공부했다.

 

[후기 및 배운 점]

 알고리즘 공부 없이 맨 땅에 헤딩하는 형식으로 하니 어렵다. 조금 강의라도 듣고 백준도 같이 풀어나가야겠다. 지금까지 학교에서 배운 것만으로 문제를 풀기에는 나는 아직 아깽이다..

연이은 "틀렸습니다"만 보다가 "맞았습니다" 보니까 너무 좋았다 ㅠㅠ

 

재밌었다.

 

#재귀함수에서 재귀함수로 미리 호출한 값을 저장하고 함수 호출을 최소화하는 방법.

#거듭제곱 및 나머지 연산의 특성. - 수학에 관련된 내용. 

#시간초과 나면 바로 다른 방안을 찾을 것.

#값 연산할 때 무조건 확실히 할 것.(사칙연산 등등)

#이번에 int형 값 범위 나가서 오류났을 때 해결한 건, long long 사용한 것 기억.