[알고리즘] 백준 1629 곱셈 // 지수승은 재귀로

* 풀이1

• a^b를 for문으로 구하는방법
• 중간중간에 %c
• 복잡도가 터진다. O(20억)

 

* 풀이2

• 이걸 재귀함수로 /2 해가면서 구하면
• log2 b 로 줄일수있다!

 

ret라는 변수에 각각의 return 값을 저장

• b가 홀수인경우, a를 1번더 곱해주면된다. ( 2^5 = 2^2 * 2^2 * 2^1)
• 각각의 18번째줄의 return 문을 만나면서, 계산한 값을 위로 계속 전달해준다!!
• return을 받은 위쪽 노드는 15번째 줄부터 수행하면서 다시 계산후, 위 노드에게 값을 전달한다.
• 최초 호출 노드를 만나면 main에서 값이 출력된다.

 

* 전체코드