[BOJ/1629/Golang] 백준 1629 - 곱셈

접근 방식

처음엔 그냥 막 곱하면 되는 줄 알았습니다.

생각해보니 21억번을 제곱하려면, 그냥 곱해서는 안 되고, memoization이라도 해야하나 싶었습니다. 하지만 memoization도 적당히 공간을 잡아야 쓸 수 있지, 21억 개를 모두 배열에 넣는 건 무리수라고 봤습니다.

문제 분류를 보니, 분할정복을 이용한 거듭제곱 이라고 적혀있었습니다. 방법은 굉장히 간단합니다. 재귀함수를 구성해서 연속해서 반씩 쪼개어 분할정복을 하는 겁니다. 이 때 곱셈의 수가 홀수면, 짝수 하나와 홀수 하나로 나눕니다. 이렇게 되면 짝수로 나눠진 거듭제곱은 한 번 구한 값을 두 번 곱하면 되므로, 연산이 줄게 됩니다.

설명 보다는 코드를 보고 이해하시는게 더 빠를 것 같습니다.

코드

package main

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

var (
    w  = bufio.NewWriter(os.Stdout)
    sc = bufio.NewScanner(os.Stdin)
)

func init() {
    sc.Split(bufio.ScanWords)
}

func main() {
    defer w.Flush()
    A, B, C := scanInt(), scanInt(), scanInt()
    fmt.Fprintln(w, solve(A, B, C))
}

func solve(a, b, c int) int {
    if b == 1 {
        return a % c
    }
    if b%2 == 0 {
        temp := solve(a, b/2, c)
        return (temp * temp) % c
    }
    return (solve(a, b/2, c) * solve(a, b/2+1, c)) % c
}

func scanInt() int {
    sc.Scan()
    n, _ := strconv.Atoi(sc.Text())
    return n
}

마무리

여기까지 따라오시느라 고생 많으셨습니다. 만약 이 글이 도움이 되셨다면 글 좌측 하단의 하트❤를 눌러주시면 감사하겠습니다.

혹시라도 글에 이상이 있거나, 이해가 가지 않으시는 부분, 또는 추가적으로 궁금하신 내용이 있다면 주저 마시고 댓글💬을 남겨주세요! 빠른 시간 안에 답변을 드리겠습니다 😊