백준/ Class4 문제 , 백준 파이썬 1629 , 곱셈 , 분할정복

백준/ Class4 문제 , 백준 파이썬 1629 , 곱셈 , 분할정복

 

 

Check Point !   ( 해당사항 ✓체크 )

1. 막힘 없이 수월하게 풀린 문제인가?

2. 1시간이내로 풀렸던 문제인가?

3. 1시간 이상 or 며칠을 두고 풀어봤더니 풀린 문제인가?

4. 시간을 써도 도무지 풀 수 없는 문제인가?

5. 솔루션을 찾아봤는가?

-------------------------------------------------------------------------------------------

난이도 체감
1. 최상
2. 상
3. 중
4. 하


<이해도>
1. 완벽히 이해
2. 다소 헷갈리는 부분들이 있음
3. 이해 못함


<덧붙일 말>

 

<문제 출처>

 

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

1629번: 곱셈

------------------------------------------------------------------------------------------------------------------------------

 

 

시간 초과 코드

 

처음 접근은 나머지들이 반복되는 점을 이용해서 풀려고 하였다. 

 

하지만 워낙 수가 크다보니 이것마저 시간초과 발생

 

 

 

 

솔루션을 찾아보니 Divide and Conquer 로 다들 풀었더라

 

분할 정복이라는 것인데, 수가 너무 크다보니 말 그대로 분할하면서 답을 도출해내는 것이다.

 

 

예를들어, 10 ** 6 % 7 이 주어지면 분할계산을 하면 된다.

 

(10 ** 3)(10 ** 3)

 

10 ** 3 은 또 (10 ** 2) * 10 이렇게 분할을 해나갈 수 있다.

 

이런 식으로 계산하면 O(lgN) 시간 복잡도가 나와 보다 더 빠르게 연산을 수행할 수 있다.

 

 

 

 

 

 

 

 

 

 

------------------------------------------------------------------------------------------------------------------------------

 

정답