분할정복

[c++] 백준 1629 풀이 ( 곱셈, 분할 정복을 이용한 거듭제곱, long long )

이 문제는 예전에 파이썬으로 풀었던 적이 있다. 그러나 c++풀이는 또 다른 포인트가 있기때문에 다시 풀어보기로 했다. 일단 문제를 쓱 보자 문제를 보면 A를 B승하고 C로 나눈 나머지를 구하라는 뜻이다. A,B,C 모두 21억을 넘는다. 이는 int의 최댓값 범위이다. 그렇다면 A^2일때 int를 넘어가서 오버플로우가 난다. 따라서 int보다는 long long을 사용하여 함수를 작성하는게 좋을 것 같다. long long의 범위는 9,223,372,036,854,775,807 이다. 그런데 A는 21억이기 때문에 long long범위를 초과할 가능성도 있다고 생각했다. 21억에 붙은 0은 9개, long long 범위의 0개수는 18개이다. 즉, 연산중에 long long범위를 초과할 가능성이 존재하..

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

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