[C++] 백준 1009번 - 분산처리 (거듭제곱의 분할정복)
문제
재용이는 최신 컴퓨터 10대를 가지고 있다. 어느 날 재용이는 많은 데이터를 처리해야 될 일이 생겨서 각 컴퓨터에 1번부터 10번까지의 번호를 부여하고, 10대의 컴퓨터가 다음과 같은 방법으로 데이터들을 처리하기로 하였다.
1번 데이터는 1번 컴퓨터, 2번 데이터는 2번 컴퓨터, 3번 데이터는 3번 컴퓨터, ... ,
10번 데이터는 10번 컴퓨터, 11번 데이터는 1번 컴퓨터, 12번 데이터는 2번 컴퓨터, ...
총 데이터의 개수는 항상 ab개의 형태로 주어진다. 재용이는 문득 마지막 데이터가 처리될 컴퓨터의 번호가 궁금해졌다. 이를 수행해주는 프로그램을 작성하라.
입력
입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 그 다음 줄부터 각각의 테스트 케이스에 대해 정수 a와 b가 주어진다. (1 ≤ a < 100, 1 ≤ b < 1,000,000)
출력
각 테스트 케이스에 대해 마지막 데이터가 처리되는 컴퓨터의 번호를 출력한다.
접근
문제가 너무 쉽게 풀렸다 (물론 틀렸음 ㅋ)
T의 수만큼 a,b를 입력받고 pow함수를 사용해서 거듭제곱을 구했다
그리고 %10을 해서 일의자리를 구하면 끝이다 어차피 컴퓨터는 10개이기 때문이다
근데 당연히 틀렸다 ... 역시 쉽게 맞출리가...
7의 100승은 수가 너무 커져서 int형을 쓰면 오버플로우가 발생한다
그래서 int형 대신 long long형을 썼다
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <math.h>
using namespace std;
using i64 = long long;
int main() {
i64 t;
scanf("%lld", &t);
for (int i = 0; i < t; i++) {
i64 a, b;
scanf("%lld %lld", &a, &b);
i64 c = pow(a, b);
i64 result = c % 10;
printf("%lld", result);
}
return 0;
}이렇게하면 될줄알았는데 여전히 답은 처음과 똑같았다. 적은 수는 정답이지만 큰 수에서는 오답이다
알고보니!!!!!!!!!!! pow(a,b)함수는 double자료형을 반환하기 때문에 계산 결과의 범위가 double자료형의 표현 범위를 벗어나면 오버플로우가 발생한다
그래서 저 함수를 쓰는대신 다른 방법으로 거듭제곱을 계산해야한다...
대표적으로 분할정복방식이 있다 그래서 문제 제목이....
크게 재귀함수를 사용하는 방법과 반복문을 사용하는 방법 두 가지가 있는데 반복문을 사용했다
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <math.h>
using namespace std;
using i64 = long long;
i64 power(i64 a, i64 b) {
i64 c = 1;
while (b > 0) {
if (b % 2 == 1) {
c *= a;
}
a *= a;
b /= 2;
}
return c;
}
int main() {
i64 t;
scanf("%lld", &t);
for (int i = 0; i < t; i++) {
i64 a, b;
scanf("%lld %lld", &a, &b);
i64 c = power(a, b);
i64 result = c % 10;
printf("%lld", result);
}
return 0;
}흠 근데 답은 다른데 여전히 오답이다.
틀린 이유를 찾아봤는데 여전히 범위초과이다
우선 분할 정복으로 계산한 것이 범위를 초과하지 않는 이유는 알고리즘 특성상 입력값이 커질수록 계산 횟수가 적어진다
그런데 나는 단순한 for문을 사용했기 때문에 입력값이 커질수록 계산횟수가 증가하니까 도중에 long long범위를 초과할 수 있다
결론 : 반복문을 써서 범위초과함
코드
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <math.h>
using namespace std;
using i64 = long long;
i64 power(i64 a, i64 b) {
i64 c = 1;
while (b > 0) { //더이상 곱할게 없을때까지
if (b % 2 == 1) { //지수가 홀수라면 a곱함
c = (c*a)%10;
}
a = (a * a) % 10;
b /= 2;
}
return c;
}
int main() {
i64 t;
scanf("%lld", &t);
for (int i = 0; i < t; i++) {
i64 a, b;
scanf("%lld %lld", &a, &b);
i64 c = power(a, b);
if (c == 0) {
printf("10\n");
}
else {
printf("%lld\n", c);
}
}
return 0;
}리뷰
거듭제곱의 분할정복의 원리는 이렇다
1. 지수가 홀수일 경우 결과값에 밑을 한 번 곱한다
2. 짝/홀 상관 없이 밑을 제곱한다
3. 그리고 지수를 반으로 쪼갠다
4. 0이 될때까지 반복한다
이걸 power함수에 적용시켰고 %10부분을 수정했다.
틀렸던 코드에서는 main문에서 power함수의 리턴값에 %10을 했는데 %10을 함수내에서 처리했다 함수결과값이 long long 범위를 초과하는것을 방지하기 위해서!
함수내에서 처리한것은 어차피 a^b의 마지막 자리수만 필요하니까 기존의 분할정복 코드에서 %10만 추가해줬다
그리고 여기서 실수한게 0일경우인데 0이라는 컴퓨터는 없으니까 0일때는 10을 출력해주는 조건만 추가해주면된다
출처