[백준 1629번] 곱셈- java

문제 설명

1. A, B, C가 주어진다.

2. A를 B만큼 곱하고 이를 C로 나누는 문제이다.

풀이 과정

 1. 당연히 그냥 구하면 터진다.

 2. 이걸 생각하면 쉽다.

       A^16 = (((A^2)^2)^2)^2

       A^17 = A*(((A^2)^2)^2)^2

 3. long형 함수에 B번 반복하기 위해 B를 인자로 넣고 재귀함수를 돌린다.

 4. 그 다음 재귀에서 구해진 값을 재곱하고 C로 나누는 것을 반복하면 된다.

 5. 그리고 인자가 홀수가 되면 그냥 A를 곱해주면 되는데, 이 이유는 홀수 인자를 갖는 경우는 재귀함수가 인자 1을 가질때까지 반복되거나, 시작할 때 홀수인 경우 두 개 밖에 없기 때문이다.

 6. 조금만 생각하면 쉽게 구현할 수 있는 문제이지만, 아이디어를 구현하는것에서 문제가 생기면 오래 걸릴 수 있을 것 같다.

코드