재귀에 고정관념을 버리자

백준 1629 풀이 (곱셈, 분할정복, 파이썬)

이번 문제 상당히 어려웠다. 심지어 풀이로직보고 코드를 짜보았는데 96%까지 올라가고 계속 틀리길래 진짜 머가 문제인지 한참 헤맸다. 문제를 보면 어찌보면 상당히 간단하다. a**b % c를 하면 시간이 상당히 오래걸리니까 이걸 분할정복으로 풀어보라는 소리다. 솔직히 이거 재귀쓰면 더 오래걸릴거 같아서 손을 계속 못댔다. 그래서 고수의 풀이를 살짝 봤더니 b를 분할해서 구하는 것을 알 수 있었다......ㄷㄷ 천재인가 진짜 상상도 못했다. 분할이니까 무언가를 분할해야한다고 생각했다면 접근했을수도 있었지만 재귀면 무조건 오래걸린다는 생각에 갇혔던 것이었다....... 여튼 원리는 아래와 같다. 10**10 = 10**5 x 10**5 로 만들 수 있다. 10**5 = 10**2 x 10**2 x 10 으로..