[백준] 1629번: 곱셈 - Python

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

1629번: 곱셈

아이디어1 (시간초과) 

• 일단 단순하게 b번 반복하며 a 곱하기
• 파이썬은 자동으로 동적할당이 되어 너무 큰 수가 나오면 메모리초과가 나올 수 있음
• a를 곱하고 c로 바로바로 나눠주며 메모리초과 방지

import sys
input= sys.stdin.readline

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

for i in range(b):
    a *= a
    a %= c

print(a)

• 단순히 반복하는 로직은 답이 아닌듯 하다.

 

아이디어 2 (시간초과)

• 반복문의 횟수를 줄 일 방법을 찾아야할 것 같음
• b가 a보다 크면 제곱을 이용하면 줄어들듯?
• b를 a로 나눈 몫이 a제곱의 개수 이후 나머지 만큼 a를 곱해줌 

import sys
input= sys.stdin.readline

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

if b>a:
    tmp = 0
    for i in range(b//a):
        tmp += a**a
    for i in range(b%a):
        tmp *= a
        tmp %= c
    print(tmp)
else:
    for i in range(b):
        a *= a
        a %= c
    print(a)

• 이것도 시간초과다 완전히 다른 접근법이 필요한듯 하다

 

아이디어3 (메모리 초과)

• 이게 c로 나눈 나머지를 구하는 것이니 결과값은 c를 넘을 수 없다.
• a를 곱하고 c로 나눈 나머지를 구할 때마다 나오는 수열의 규칙을 찾아보자
• 규칙이 찾아지면 b를 반복되는 수열의 개수로 나눈 나머지로 알맞은 답을 찾자
• 예외) 규칙이 한 숫자로 무한히 반복되면 그 수를 반환

import sys
input= sys.stdin.readline

a, b, c = map(int, input().split())
tmp = a
li = []

li.append(a)

for i in range(c):
    tmp *= a
    tmp %= c
    if tmp == li[0]:break
    elif li[-1] == tmp:
        print(tmp)
        exit()
    li.append(tmp)

print(li[b%len(li)-1])

• 메모리 초과 발생
• li[]에 들어가는 메모리가 최대 c(2,147,483,647개)가 들어가는 경우가 생기는 듯 하다.

아이디어 4 (성공)

• 완전히 다른 방식으로 접근을 해보자
• 분할 계산을 이용한다.
• 2^16 이라면 => 2^8 * 2^8 => 2^4*2^4  * 2^4*2^4
• 이런식으로 불필요한 계산을 줄여주는 방법을 사용하자

def dac(a,b,c):
    if b == 1:
        return a % c
    
    if b % 2 == 0:
        return (dac(a,b//2,c) ** 2)%c
    else:
        return ((dac(a,b//2,c) ** 2)*a)%c

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

마무리

• 지금까진 참신한 방법이 떠오르고 오 좋을 것 같은데? 라는 생각이 들면 시간복잡도와 메모리적인 측면은 깊게 생각하지 않고 문제를 풀어왔던 것 같다.
• 앞으로 창의적인 방법도 좋지만  귀찮더라도 메모리와 시간복잡도에 있어서 얼마나 효율적인지 정확히 따지는걸 습관화 해야겠다.