[python/파이썬] 백준 1629 곱셈

[문제 출처]

https://www.acmicpc.net/status?user_id=taeyeon357&problem_id=1629&from_mine=1 

채점 현황

 

[문제 풀이]

 

a, b, c 세 개의 숫자가 주어졌을 때,

a를 b번 곱해준 수를 c로 나눴을 때의 나머지를 구하는 문제이다.

 

만일 문제에 주어진 대로 코드를 작성한다면

print((a**b)%c)로 쓸 수 있다. 하지만 수가 기하급수적으로 커지기 때문에 시간초과가 발생한다.

따라서 다른 방법을 사용해야 한다.

 

 

분할 정복을 이용하면 제곱을 더 빨리 할 수 있기 때문에, 분할 정복을 이용하여 코드를 작성하였다.

 

아래의 코드를 이해하기 위해서는 2가지 개념을 알아야 한다.

1️⃣ 지수 법칙

a^m * a^n = a^(m+n)

2️⃣ 나머지 연산의 분배 법칙

(A*B) % C = ((A%C) * (B%C)) % C

 

위의 두 가지 개념을 이용해서 아래 코드들을 작성하였다.

 

 

✅소스 코드1 - 시간 초과

 

처음에는 제곱의 시간만 줄이면 해결할 수 있을 거라고 생각해서

제곱만 함수를 따로 작성하였으나 시간초과가 발생하였다.

def power(a,n):
  if n == 0:
    return 1
  
  if n == 1:
    return a
  
  x = power(a,n//2)
  if n%2==0:
    return x * x
  else:
    return x * x * a

a, b, c = map(int, input().split())

print(power(a,b)%c)

 

✅소스 코드2 - 맞았습니다!!

 

시간 초과를 막기 위해서 함수 내에서 나머지 연산을 한 값을 반환해 주었다.

위의 코드와 거의 동일하나 나머지 연산이 추가되었다.

a,b,c = map(int,input().split())

def power(a,b):
  if b == 1:
    return a % c

  x = power(a,b//2)
  if b%2==0:
    return (x * x) % c
  else:
    return (x * x * a) % c


print(power(a,b))