title: 백준 1629 곱셈
date: "2021-15-11T03:00:00.169Z"
template: "post"
draft: false
slug: "백준 1629 곱셈"
category: "Coding test"
tags:
- "Coding test"
description: "백준 1629 곱셈"
백준 1629 곱셈
문제 이해
자연수 A를 B번 곱한 수를 알고 싶다. 단 구하려는 수가 매우 커질 수 있으므로 이를 C로 나눈 나머지를 구하는 프로그램을 작성하시오.
즉, A**B%C 를 구하라는 말이다.
접근 방법
문제를 풀기전에 미리 하나의 수학적 지식을 알 필요가 있다. 아래의 이유로 두 수의 곱의 나머지는 각각의 나머지의 곱의 나머지와 같다는 것을 알 수 있다.
이 문제를 내가 생각한 두 가지 풀이로 풀었는데 두개 다 틀리고, 구글링을 통해 분할정복 알고리즘이란 것을 이용해야한다는 것을 알게 되었다.
풀이
첫 번째 풀이 : 문제에서 요구한 그대로 A**B%C를 썼다. 시간 초과에 걸린다. 이유는 A,B,C 가 굉장히 큰 범위로 설정되어 있기 때문이다.
두 번째 풀이 : 주기를 찾아 푸는 방법으로 풀었다. 내용은 아래와 같다.
이런 식으로 반복되는 패턴을 보일 것이라고 생각했다.
예를 들어,
한 주기 내에 들어갈 값을 구하고 한 주기의 길이를 제곱하는 횟수로 나눈 나머지를 이용해 답을 구할 수 있다.(고 생각했다.)
a, b, c = map(int, input().split())
period = []
length = 1
value= 1
while True:
value = value * a
value = value % c
if value in period:
length = len(period) - period.index(value)
break
else:
period.append(value)
delete_num = len(period)-length
if b>delete_num:
for _ in range(delete_num):
period.pop(0)
print(period[(b - delete_num-1)%length])
else:
print(period[b-1])이 풀이의 문제점은 C 또한 엄청나게 커지면 한 주기의 크기 또한 커질 것이기 때문에, 주기를 구하는 데에도 오래 걸릴수 있다는 문제가 있다.
시간복잡도: N(최악의 경우)
세 번째 풀이: 구글링을 통해 찾은 분할정복 알고리즘 풀이
위와 같은 방법으로 나누어서 생각할 경우. 지수가 홀수일 때는 제곱한 후 a의 값을 곱하고, 지수가 홀수일 때는 제곱만 한다.
def power(a, b, c) :
if b==1:
return a % c
else:
temp = power(a, b//2,c)
if b%2 ==1:
return (temp*temp*a) % c
else:
return (temp*temp) % c
a, b, c = map(int, input().split())
print(power(a,b,c))
시간복잡도 : O(log(N))
네 번째 풀이: 지수를 이진수로 변환하여 풀기
이 방법은 a%c를 구하고 이를 제곱한 다음 곱하기만 해서 답을 구할 수 있는 방법이다.
def answer(a, b, mod):
ret = 1
while b:
if b%2 ==1:
ret = ret * a % mod
a = a * a % mod
b //= 2
return ret
a, b, c = map(int, input().split())
print(answer(a,b,c))시간복잡도 : O(log(N))
