ps
-
[백준 1629] 곱셈 python (수학)study/PS 2021. 2. 4. 22:49
자연수 A를 B번 곱한수를 만들고 이를 C로 나눈값을 출력하면 된다. A ** B % C 하면 될 것 같지만 시간 복잡도 O(B)이기 때문에 시간 초과한다... 매우 크게.. 이때 이진수를 활용하면 빠르게 풀이 할 수 있다. 아이디어 : 거듭제곱은 거듭제곱 간의 곱으로 표현 가능하다. A^13이라는 값을 이진수로 표현하면 A^1101이 되는데 1101 / 2 => 110 ... 1 110 / 2 => 11 ... 0 11 / 2 => 1 ... 1 1 / 2 => 0 ... 1 이렇게 2로 나누면 나머지가 원래 가지고 있던 이진수가 됨을 알 수 있다. A^13 = A * A^4 * A^8 조건문 + N진수 변환 방법으로 해결 가능하다는 것을 알 수 있다. def answer(a, b): ret = 1 w..