[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, &C);

	int *bList = (int *)malloc(sizeof(int) * 100);
	int *mList = (int *)malloc(sizeof(int) * 100);

	printf("%d", memsolve(A, B, C, bList, mList));

	free(bList); free(mList);

	return 0;
}

cnt는 메모이제이션 배열의 인덱싱을 위해 만든 변수이고(재귀 함수에서 사용할 것이기 때문에 전역변수로 선언), bList는 거듭제곱 수를 저장하는 배열, mList는 해당 거듭제곱 수로 연산했을 때의 나머지를 저장하는 배열입니다. 따라서 두 배열은 항상 같은 인덱스를 참조합니다. 구조체를 이용하는 것이 더 나았을 수도 있겠네요.

우리는 문제에서의 B(거듭제곱 수)를 반씩 나눠갈 겁니다. 그 과정에서 나오는 모든 B 값을 저장할 수 있는 크기의 배열이 필요하겠죠. 예를 들어 B에 4가 입력된 경우 4 → 2 / 2 → 1 / 1 / 1 / 1으로 변화하며 총 3칸의 배열이 필요하게 됩니다. 다만 2의 제곱수가 아닌 경우에는 또 다릅니다. 예를 들어 5 → 2 / 3 → 1 / 1 / 1 / 2로 총 3칸의 배열이 필요하겠네요.

수가 짝수이면 같은 두 수로 분할되지만 수가 홀수이면 다른 두 수로 분할될 겁니다. 어떤 홀수를 분할하면 짝수 + 홀수로 나누어지므로 분할하는 모든 과정이 홀수인 수는 1을 제외하면 없습니다. 그러나 배열 칸수가 부족하지 않게 분할하는 모든 과정이 홀수인 수 n이 있다고 가정하면 칸수는 log_2(n)만큼이 필요하겠네요. 문제에서 B의 최대 크기는 INT_MAX입니다. log_2(INT_MAX)는 32에 가까우므로 메모이제이션 배열을 100칸 정도로 선언해 두면 인덱스가 부족할 일은 없을 것입니다. 따라서 저는 100칸으로 선언했습니다.

 

2. 분할정복 함수

int memsolve(int A, int B, int C, int *bList, int *mList) {
	int tmp = getIndex(bList, B);
	if (tmp == -1) {
		int idx = cnt++;
		int B1 = B / 2;
		int B2 = B - B1;

		bList[idx] = B;
		if (B == 1)
			mList[idx] = A % C;
		else {
			int B1 = B / 2;
			int B2 = B - B1;

			mList[idx] = ((long long)memsolve(A, B1, C, bList, mList) * (long long)memsolve(A, B2, C, bList, mList)) % C;
		}
		
		return mList[idx];
	}
	else {
		return mList[tmp];
	}
}

getIndex 함수는 배열에 찾는 값이 있으면 해당 값의 인덱스를(메모이제이션하므로 중복은 없음) 반환하고, 없으면 -1을 반환합니다. 따라서 위 함수의 첫 번째 분기는 그저 메모이제이션을 위한 것이고 해당 분기에서 조건(tmp == -1)을 만족하는 경우 두 번째 분기가 시작됩니다. 만약 B == 1이면(더 이상 분할할 수 없는 상태) A % C를 반환합니다. 그렇지 않은 경우 문제를 분할하고 이번 글의 서두에서 언급한 공식을 이용하여 재귀적으로 처리합니다.