백준 - 1629 곱셈 (feat. Python)

문제 출처

https://www.acmicpc.net/problem/1629

우선 문제를 푸는데 시간초과가 나올 것 이라 생각했지만 도무지 수학적머리가 안 돌아가보니 이해에 꽤 많은 시간을 들였던 문제였다.(Feat 수능 수학 나형)

문제를 푸는데 참고에 도움을 주신

풀이 이해 및 참고

여기서 코드를 전체적으로 참고

거듭제곱에 대한 문제 이해를 여기서 했습니다

---

♻ 이해한 문제 풀이 방식

여기서 경우는 두가지가 나온다 2로 나누어 떨어질 때까지 우리는 계속 나눌 것인데
¹ 2로 끝까지 나누어 떨어지는 수가 있는 반면 위의 사진처럼 ²거듭제곱으로 묶이지 않고 한 개가 남게 되는 경우이다.

🚀코드를 참고하여 이해했다.

참고한 풀이방식처럼 우리는 저 '?'를 재귀함수를 통해 계속 구해나간다.
=> 2로 계속 나누며 거듭제곱으로 구할 것이다.

• 그렇기 때문에 홀수가 나오면 'a'를 따로 빼서 곱해줘야 한다.
  • 저 형식으로 계속 구해나간다고 생각해주면 된다