[BOJ #1629] 곱셈 BOJ #1629, 곱셈 문제입니다. 문제의 이름과는 다르게 정답률이 낮고 살짝은 까다로울 수 있는 문제입니다. 이 문제는 분할정복법으로 풀게 되며(Divide & Conquer), 따라서 재귀를 사용합니다. 또 (A * B) % C == ((A % C) * (B % C)) % C임을 알고 있어야 합니다. 저는 처음에 이 공식을 몰랐으나 아주 예전 BOJ #10430, 나머지 문제를 푼 것이 기억나 사용하게 되었습니다. 추가적으로 분할정복만으로는 시간 초과가 떠서 메모이제이션(memoization)까지 사용하였습니다. 1. main에서의 array for memoization 생성 int cnt = 0; int main(void) { int A, B, C; scanf("%d %d %d", &A, &B, .. 2020. 8. 2. 이전 1 다음