[백준_1629_곱셈]
https://www.acmicpc.net/problem/1629 문제 설명 자연수 A를 B번 곱한 수를 알고 싶다. 이를 C로 나눈 나머지를 구하는 프로그램을 작성하시오. A, B, C가 빈 칸을 사이에 두고 순서대로 주어진다. A, B, C는 모두 2,147,483,647 이하의 자연수이다. 문제풀이 전형 적인 분할 정복 문제이다. B가 2,147,483,647라면 완전 탐색으로는 시간 초과가 된다. 따라서 O(logB)가 나오는 분할 정복으로 풀이한다. 순서 재귀를 사용한다. 종료 조건을 1일때 A%C를 반환으로 컷한다. 그 이외의 경우 재귀적으로 go(B/2)을 으로 반환 값을 구한다. B/2가 짝수이면 go(B/2)*go(B/2)%C B/2가 짝수라면 (go(B/2)*go(B/2)*A)%C로 2..
2021. 4. 12.
