백준 1629. 곱셈 문제

BOJ 1629 곱셈 문제

문제 설명

무턱대고 단순 재귀함수나 반복문으로 접근했다가는 크게 뒤통수 맞을 수 있는 문제였습니다. (하하하….;;;) 만약 당신이 지금 그러고 있다면 당장 때려 치십쇼.

우선 이 문제에서 주목해야 할 점은 시간제한입니다. 시간복잡도를 고려해야 한다는 소리이겠죠. 그리고 입력값의 크기입니다. 막 곱했다가는 overflow나기 딱 좋죠.

분할정복을 이용한 거듭제곱

단순히 재귀나 for loop로 거듭제곱을 했다가는 시간초과가 발생할 겁니다. 그렇다면 더 효율적인 거듭제곱 방식이 존재할까요??

바로 그게 분할정복입니다.

  • a^(2t) = a^t*a^t
  • a^(2t+1) = aa^ta^t 위 유도식을 살펴보면 a^t라는 중복되는 값이 등장하는 것을 확인할 수 있습니다. 다시말해 a^t를 일일이 구하지 않고 하나를 구해서 복붙해서 사용하면 된다!라는 뜻이죠~~~

당연히 for loop보다 빠릅니다.

정답 코드

#include <stdio.h>

long long int f(int i, int j, int c) {
	if (j == 1) {
		return i % c;
	}

	long long tmp = f(i,j/2,c);
	if (j % 2) {
		return i * (tmp*tmp % c)%c;
	}
	else {
		return tmp * tmp % c;
	}
}

int main() {
	int a, b, c;
	scanf("%d %d %d", &a, &b, &c);
	printf("%lld", f(a, b, c));
}

여담

처음에는 ‘아 백만년만에 문제푸는 거니깐 쉬운거 해야징’하고 대충 제목이 쉬워보이는 요친구를 풀기로 했는데. 쉽기는 무슨 거의 핵폭탄이었습니다.

일단 처음에는 핵폭탄인줄 모르고 걍 재귀를 썼죠.

#include <stdio.h>
int f(int a, int n, int c) {
	if(n>0) {
		return f((a*a)%c,n-1,c);
	}
		
	else
		return a;
}

int main() {
	int a,b,c;
	scanf("%d %d %d", &a,&b,&c);
	printf("%d", f(a,b,c)%c);
}

아니근데 시간초과가 나길래 매모제이션 쓰라는건가?해서

#include <stdio.h>

int memo[2147483647];
int cnt = 0;

int f(int a, int b, int c, int k) {
	if(b>1) {
		if(k == memo[0]) {
			return memo[(b+1)%cnt];
		}
		else {
			memo[cnt]=k%c;
			cnt++;
			return f(a,b-1,c,k*a%c);
		}	
	}
	else {
		return k%c;
	}
}

int main() {
	int a,b,c;
	scanf("%d %d %d", &a,&b,&c);
	printf("%d", f(a,b,c,a));
}

요 코드처럼 그냥 재귀+메모제이션 이용해서 풀면 되것지~ 했는데 아니 그런 방식으로는 절대로 안풀리지 뭡니까??여기에서 선배한테 SOS 쳤습니다…. 코드에서 볼 수 있듯 저딴 배열이 작동할 리가 없죠.

진짜 한 2시간 해매다가 선배찬스 썼는데 웬걸. 내가 푼 방식은 완전 틀린 것이였더라….(진심 감사합니다….. 이상한거에 삽질 죽어라 할뻔…. 이미 2시간 삽질하긴 했지만)

이자리를 빌어 다시한번 Son선배님께 감사의 말을 전합니다~~~~~~~~~~

그 이후에도 메모제이션에 집착하다가 걍 배열 자체를 쓰면 안된다는 사실을 다시 깨달았고….;(배열 크기가 막 몇억 되어야함)

#include <stdio.h>
long long int m[50]={};
long long int f(int i, int j, int c) {	
	if(j==1) {
		return i%c;
	}
	if(m[j]) {
		return m[j];
	}
	else if(j%2) {
		return m[j] = i*f(i,j-1,c)%c;
	}
	else {
		return m[j]=f(i,j/2,c)*f(i,j/2,c)%c;
	}
}

int main() {
	int a,b,c;
	scanf("%d %d %d", &a, &b, &c);
	printf("%d", f(a,b,c));
}

배열 없애기 작업 후! 성공했다고 한다….. 4시간만에 ㅋ

이거 못풀었으면 꿈에 이 문제 나왔을 듯. 이 사진은 고생과 바보짓의 흔적이라고 해두죠. BOJ 1629 곱셈 문제 (맞았습니다!보고 진짜 감격의 눈물 흘릴~뻔)

진짜 가끔 이렇게 혁신적인 알고리즘 만날 때마다 문제 풀때는 좀 빡치는데 그만큼 재미있는것 같습니당. 근래 1달간 가장 알찬 활동이었다고 한다…….