[BOJ] 1629 곱셈 (C/C++)

1629번: 곱셈

문제

자연수 A를 B번 곱한 수를 알고 싶다. 단 구하려는 수가 매우 커질 수 있으므로 이를 C로 나눈 나머지를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어진다. A, B, C는 모두 2,147,483,647 이하의 자연수이다.

출력

첫째 줄에 A를 B번 곱한 수를 C로 나눈 나머지를 출력한다.

---

문제를 보자마자 이전에 풀었던 분할 정복을 사용한 거듭제곱이 생각났다. 그래서 쉽게 풀 수 있었다.

 

그래도 유의할 점이 하나 있었다고 한다면 입력이 int가 가질 수 있는 최댓값까지 들어올 수 있기 때문에 안전하게 long long을 사용했다. 그런데 3%쯤에서 틀렸습니다가 나왔다. 곰곰이 생각해보니 A = A * A 이 부분에서 A가 long long의 범위를 벗어날 수도 있을 것 같았다. 그래서 % 연산을 추가하고 pass를 받을 수 있었다.

 

 

후기)

문제 난이도가 실버1이라 쉽게 풀었지만, 거듭제곱하는 방법을 몰랐다면 쉽게 가지 못했을 것 같다.