티끌모아 태산

[백 준/구현] 1629: 곱셈 본문

백준 문제/문자열,누적합,구현

[백 준/구현] 1629: 곱셈

goldpig 2024. 1. 1. 18:27
728x90

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

 

1629번: 곱셈

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

www.acmicpc.net

핵심 아이디어

  • 이 문제는 단순하게 풀면 바로 시간초과가 발생합니다. 따라서 분할정복원리를 활용해서 풀어야합니다.

예를 들어, 2^32라면 2를 32번 곱하는 방법도 있지만, (2^16)^2로 해서 풀면 2를 16번 곱한 것을 다시 2번 곱하니 17번의 연산만으로 끝낼 수 있어 시간이 훨씬 적게 듭니다. 이를 계속 해보면 {(2^8)^2}^2 이렇게 풀면 10번만에, [{(2^4)^2}^2]^2 이렇게 풀면 7번만에 끝낼 수 있어 시간이 획기적으로 주는 것입니다.

 

풀이

import sys
input = sys.stdin.readline
a, b, c = map(int, input().split())

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

result = dac(a,b,c)
print(result)

분할정복 함수를 구현해서 풀었습니다. 처음에는 어떻게 접근해야하는지 모르겠어서 다른 사람들의 코드를 참고하여 풀었습니다. 

 

참고 블로그:https://my-coding-notes.tistory.com/93

 

[🥈1 / 백준 1629 / 파이썬] 곱셈

1629번: 곱셈 첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어진다. A, B, C는 모두 2,147,483,647 이하의 자연수이다. www.acmicpc.net 문제 자연수 A를 B번 곱한 수를 알고 싶다. 단 구하려는 수가 매

my-coding-notes.tistory.com

 

 

728x90

'백준 문제 > 문자열,누적합,구현' 카테고리의 다른 글

[백 준/구현] 4375: 1  (0) 2024.01.02
[백 준/구현] 9375: 패션왕 신해빈  (0) 2024.01.01
[백 준/구현] 2559: 수열  (0) 2024.01.01