[JAVA] 백준 1629번 곱셈

알고리즘

by dajingjing 2022. 4. 11. 11:49

1629번: 곱셈

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

www.acmicpc.net

요즘 CODE 책을 읽으면서 이진수에 대해 흥미가 생겨 이진수를 이용해서 푸는 방법으로 풀어보았다.

10을 11번 곱한 수를 12로 나눈다고 할 때,

10을 11번이나 곱하는 것은 비효율적이므로 2진수를 이용해서 구해보자.

11을 이진수로 나타내면 1011 → 2^3 + 2^1 + 2^0 → 8 + 2 + 1

10^11 = 10^(8+2+1) = (10^8) x (10^2) x (10^1)

11을 이진수로 나타낼때 1011 이면, 11을 2로 나누어 나머지가 1인 경우 부터 0이 되기 전까지,

11을 2로 나누었을때 나머지가 1이면, 2진수 자리수 만큼 10을 곱한 수를 곱해준다..

1011 에서 오른쪽부터 왼쪽으로(←) 처음은 10을 곱하고 그다음은 10의 제곱을 곱하고(100이 됨),

그다음은 100의 제곱(10000이 됨)이지만 0이라서 곱해주지 않고, 그다음은 10000의 제곱을 곱한 값.

여기까지는 풀었는데 그 다음에서 내가 간과한 것이 있었다.

제곱수가 너무 커져서 long 범위 안에도 들지 못한 것이다.

이때 사용하는 모듈러 연산의 곱셈 성질이다.

(A * B) mod C = (A mod C * B mod C) mod C

위 내용에 대한 증명은 아래 사이트에 나와있다.

모듈로 곱셈 (개념 이해하기) | 암호학이란? | Khan Academy

ko.khanacademy.org

모듈러 연산은 덧셈, 뺄셈은 알고 있었어도 곱셈은.. 이제 알았다.

ans *= mul 이 아니라 ans = (ans*mul)%mod

mul *= mul 이 아니라 mul = (mul*mul)%mod

곱셈도 잊지말자!