백준 1629 곱셈 (실버 1)

백준 1629 곱셈 (실버 1)

링크: 1629 곱셈

---

접근 방법

• (시간 초과) 반복문으로 계산하고 그 중간 과정에 C로 나눔
• (정답) 분할 정복으로 지수를 나눠서 계산

---

소스 코드

소스 코드: 93356067 제출

A, B, C = map(int, input().split())
# print(pow(A, B, C)) 정답

def divide(A: int, B: int) -> int:
    if B == 0:
        return 1
    half = divide(A, B//2)
    if B % 2 == 0:
        return (half * half) % C
    else:
        return (half * half * A) % C

print(divide(A, B))

A	B	C	return
10	11	12
'''	5	'''
'''	2	'''
'''	1	'''
'''	0	'''	1
'''	1	'''	10
'''	2	'''	4
'''	5	'''	4
'''	11	'''	4
최종값			4

• 솔직히 감이 잘 오지 않아서 비공개 처리했다..

---

코드 개선 사항(GPT 4o)

---

결론

• 분할 정복 문제를 마주칠 때마다 감이 전혀 안잡힌다.
• 그리고 분할 정복을 써야하는 이유를 들었을 때도 오... 음.. 그런가.. 싶다.. ㅋㅋ
• 분할 정복 문제가 귀했는데, 문제 복잡도가 낮았어서 쉽게 날린 것 같아 아쉽다 ㅠ