문제: https://www.acmicpc.net/problem/1629
이번 1629번 문제를 통해서 알아볼 개념은 분할정복입니다.
이는 딱 명확한 알고리즘이 존재하는 것이 아닌, 구하려는 값이나 그 과정이 너무 계산하기 복잡할 때 이를 간단한 문제들로 쪼개서 푼 뒤, 이를 합친다라고 생각하면 되는데요.
당장에 웹개발을 한참 공부하고 있는 저는 main.js 파일에 너무 많은 코드를 쓰다보면 나중에 오류가 발생했을 때 수정하기 어려울 뿐더러 스스로도 알아보기 힘들어 main.js에는 여러 js파일들을 import만 하고 다른 여러 파일들을 header footer block별로 구분하여 작성하는데요. 이 역시도 분할정복이라고 볼 수 있습니다.
그럼 이번 문제는 왜 분할 정복 문제인가?
쉽게 생각해보면 2147483647을 2147483647번 곱하는 명령만 돌려도 하루 종일 걸리실지도 몰라요..
저렇게 큰 수를 큰 수만큼 곱하는 연산을 간단한 문제로 쪼개서 합쳐야겠죠?
저는 이 문제를 이진법으로 접근했습니다.
사실 2147483647을 10번 곱하는 건 일도 아니에요, 하지만 10을 2147483647번 곱하는 건 매우 큰 일이랍니다.
이 문제는, 어떻게 B번 곱하는 복잡한 일을 최소화 할 수 있을까에 초점을 맞추어야했어요.
그래서 저는 B를 이진수로 표현한 뒤 연산하였는데요, 예를 들어볼게요.
10 11 12 의 숫자가 주어졌다면,
원래는 10을 11번 곱해야겠지만,
11을 [1,0,1,1]로 표현한다면,
10을 1번 곱한 뒤 12를 나눈 나머지,
10을 2번 곱한 뒤 12를 나눈 나머지, (10을 1번 곱한 뒤 12를 나눈 나머지의 제곱)
10을 4번 곱한 뒤 12를 나눈 나머지는 건너뛰고, (10을 2번 곱한 뒤 12를 나눈 나머지의 제곱)
10을 8번 곱한 뒤 12를 나눈 나머지, (10을 4번 곱한 뒤 12를 나눈 나머지의 제곱)
를 구한 뒤 그것들을 곱해주면 된답니다.
연산이 총 n번에서 log2(n)번으로 줄어들게 되는거죠!
만약 2147483647번 곱하는 일이 있다면,
이는 [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] 로 치환되어 약 30번의 연산만으로 해결 가능한 문제가 된답니다.
생각보다 구현은 간단했지만, 접근을 잘못하면 결코 시간 제한을 만족시키기 힘들었던 1629번 곱셈문제였습니다.
다음은 풀이 코드입니다.
[A, B, C] = list(map(int, input().split()))
b = []
current = -1
answer = 1
# B를 이진수로 b 리스트에 담기
x = 1
while(B>=x):x *= 2
while(x!=1):
x /= 2
if (B>=x):
b.append(1)
B -= x
else: b.append(0)
# b 리스트 끝부터 시작하며 A를 B번 곱한 수를 C로 나눈 나머지를 answer에 저장
while(b != []):
K = b.pop()
if (current == -1): current = A%C
else: current = (current*current)%C
if (K==1):
answer *= current
answer %= C
print(answer)
끝!
'Programming > 백준 문제풀이' 카테고리의 다른 글
C# 문자열 백준 문제풀이 (1157, 1316, 2675, 2908, 2941, 5622) (0) | 2020.07.20 |
---|---|
백준 2805번 나무자르기 _ 이분탐색 (python) (0) | 2020.04.10 |
백준 1931번 회의실배정 _ 탐욕알고리즘 (Greedy Algorithm) (python) (0) | 2020.03.17 |
백준 2178번 미로 탐색 _ BFS (python) (0) | 2020.03.16 |
백준 2667번 단지번호붙이기 _ DFS (python) (1) | 2020.03.15 |