반응형 분할정복을 이용한 거듭제곱1 [cpp 알고리즘] 백준 1629 곱셈 [백준] 1629 곱셈 cpp 풀이 수학, 분할 정복을 이용한 거듭제곱 https://www.acmicpc.net/problem/1629 문제 요약 첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어졌을 때, A를 B번 곱한 수를 C로 나눈 나머지를 출력하면 된다. 풀이 정리 - 분할 정복을 활용하여 지수를 나누어 주면 된다. (1) 지수가 0인 경우 -> X^0 = 1 이므로 1을 리턴해준다. (2) 지수가 짝수인 경우 -> X를 X/2로 나누어서, 계산한 두 값을 곱해준다. (3) 지수가 홀수인 경우 -> X를 X/2로 나누고, 계산한 두 값과 밑을 한 번 더 곱해준다. - 예제에 나왔던 A=10, B=11로 예를 들어 보면, 1. 가장 나이브하게 먼저 생각나는 방법은 for문을 이용하여 .. 2023. 11. 10. 이전 1 다음 반응형