[백준] 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 사용한 것 기억.