[백준 / C++] 1629번: 곱셈 (그리디 풀이...?)

 

 

 

 

https://www.acmicpc.net/problem/1629

 

1629번: 곱셈

난이도: solved.ac 실버 1

 

 

분할 정복(Divide and Conquer)을 이용해 푸신 분들이 많던데 나는 그리디(?)로 풀어보았다.

 

A를 B번 곱하는 것은 A의 B승을 구하라는 것과 같다.

 

따라서 A를 A^B로 만들어주기로 했다.

 

A는 A^1이다.

 

A^1을 A^B로 만드는 과정은 1을 B로 만드는 과정과 같다.

 

우선 거듭제곱의 성질 중 a^b * a^b = a^(2b) 를 알아야 한다.

 

2^3 * 2^3 = 2^6 (8 * 8 = 64)을 떠올리면 이해하기 쉽다.

 

시간 제한이 0.5초로 매우 짧은데, 시간 내에 풀기 위해서는 연산 횟수를 최소화 해야한다.

 

위의 성질을 이용해 1에 계속 2를 곱하면서 B보다 작거나 같은 2의 제곱(1, 2, 4, 8, 16, 32, ...)으로 만들어 B가 0이 될 때까지 B에서 그 값을 빼는 과정을 반복하면 연산 횟수를 최소화 할 수 있다.

 

예를 들어 1을 13으로 만드는 과정을 나열해보면,

 

1) 13보다 작거나 같은 수 만들기

1 → 2 → 4 → 8           (B = 13 - 8 = 5)

2) 5보다 작거나 같은 수 만들기

1 → 2 → 4                   (B = 5 - 4 = 1)

3) 1보다 작거나 같은 수 만들기

1                                  (B = 1 - 1 = 0)

 

13 = 8 + 4 + 1으로 세 번의 연산으로 만들 수 있게 된다.

 

이 과정은 그리디 알고리즘을 활용한 '동전 0' 문제를 푸는 것과 같이 하면 된다.

https://www.acmicpc.net/problem/11047

11047번: 동전 0

 

B보다 작거나 같은 2의 n승을 찾은 후 B에서 그 수를 빼고, 그 수가 0이 될 때까지 반복하는 것이다.

 

Ex.

1 → 24 만들기

24 = 16 + 8

 

1 → 39 만들기

39 = 32 + 4 + 2 + 1

 

코드

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

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	long long A, B, C, tA, tB, ans = 1;
	cin >> A >> B >> C;
	while (B) {
		if (B == 1) {
			ans = (ans * A) % C;
			break;
		}
		tA = A;
		for (tB = 2; tB <= B; tB *= 2)
			tA = (tA * tA) % C;
		ans = (ans * tA) % C;
		tB /= 2;
		B -= tB;
	}
	cout << ans;
}

 

성능

코드 제출 결과