[Go] 백준 1629번 곱셈 (시간 복잡도 O(logN))

문제

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

입력

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

출력

첫째 줄에 A를 B번 곱한 수를 C로 나눈 나머지를 출력한다.

---

문제 풀이

문제 해석 및 계획

int 자료형의 범위를 넘어가지 않기 위하여 A를 C로 나눈 나머지를 거듭제곱하고 그 결과도 C로 나눈 나머지로 저장하려고 하였습니다.

오답 노트

실버 1문제가 이렇게 쉬운가 싶었지만 역시 시간초과에 걸리게 되었습니다.

package main

import (
	"bufio"
	"fmt"
	"os"
)

func main(){
	reader := bufio.NewReader(os.Stdin)
	writer := bufio.NewWriter(os.Stdout)

	defer writer.Flush()

	var a, b, c int64
	fmt.Fscan(reader, &a, &b, &c)
	newA := a%c
	answer := int64(1)
	for i:=int64(0) ; i<b ; i++ {
		answer = (answer*newA) % c
	}
	fmt.Fprintln(writer, answer)
}

정답

거듭제곱을 빠르게 처리할 수 있는 알고리즘이 있었습니다.

A를 연속하여 거듭제곱한다면 B번 곱하는 문제이지만 B를 2진수로 생각한다면 거듭제곱을 더욱 빠르게 할 수 있습니다.

B가 11인 경우 2진법으로 표현한다면 1011이 됩니다.

따라서 A^11을 A^8 * A^2 * A^1로 표현할 수 있으므로 아래와 같은 방식으로 계산하였습니다.

A는 제곱한 값으로 키워가므로 A -> A^2 -> A^4  ->...로 커져가므로 B를 2진법으로 표현할 때 1인경우마다 answer에 값을 곱해주면 됩니다. 이 경우 O(logN)의 시간 복잡도를 가집니다.

package main

import (
	"bufio"
	"fmt"
	"os"
)

func main(){
	reader := bufio.NewReader(os.Stdin)
	writer := bufio.NewWriter(os.Stdout)

	defer writer.Flush()

	var a, b, c int64
	fmt.Fscan(reader, &a, &b, &c)
	newA := a%c
	answer := int64(1)
	for b>0 {
		if b%2 == 1 {
			answer = (answer*newA) % c
		}
		b /= 2
		newA = (newA*newA) % c
	}
	fmt.Fprintln(writer, answer)
}

---

느낀 점

단순한 거듭제곱마저 단축할 수 있다는 것을 처음 알았습니다. 알고리즘은 끝이 없으므로 매일 꾸준히 풀어가며 많은 방식을 알아둬야 실력이 늘어난다는 것을 다시 한번 마음에 새겼습니다.