(백준 1629번 곱셈 C++) 라이님 블로그 대회 알고리즘 따라잡기 4) 분할 정복(Divide and Conquer) 3탄

분할정복이 점점 익숙해져간다! 오늘의 문제는 거듭제곱 문제!

 

이전 포스팅은 여기에!↓

2024.01.08 - [알고리즘] - (백준 1780번 종이의 개수 C++) 라이님 블로그 대회 알고리즘 따라잡기 4) 분할 정복(Divide and Conquer) 2탄

(백준 1780번 종이의 개수 C++) 라이님 블로그 대회 알고리즘 따라잡기 4) 분할 정복(Divide and Conquer)

 

백준 1629번

https://www.acmicpc.net/problem/1629

1629번: 곱셈

 

우선 문제를 보면 A, B, C의 범위를 아래와 같이 주는데, 이는 A, B, C가 int형으로 입력을 받을 수 있다는 의미이다.

다만 연산을 하다보면 int의 범위를 벗어날 수 있으므로 long long으로 문제를 풀어주는게 뽀인뜨!

#define _CRT_SECURE_NO_WARNINGS
#include <cstdio>
#include <cmath>
int cnt = 0;
long long PowerProduct(long long a, long long b, long long c);
long long Power(long long x);

int main() {
	long long a, b, c;
	scanf("%lld %lld %lld", &a, &b, &c);
	a = a % c;
	if (a == 0) {
		printf("0"); return 0;
	}
	//if (a == 0) return 0; //헉시 바보세요?

	// a < c인 경우만 고려해주면 된다.
	printf("%lld", PowerProduct(a, b, c));
	return 0;
}
long long Power(long long x) {
	return x * x;
}
long long PowerProduct(long long a, long long b, long long c) {
	cnt++;
	//printf("cnt : %d, a = %d, b = %d, c = %d\n", cnt, a, b, c);
	if (b == 2) return ((a % c) * (a % c)) % c;
	if (b == 1) return a % c;

	if(b %2 ==0) return (Power(PowerProduct(a, b / 2, c))) % c;
	else return ((Power(PowerProduct(a, b / 2, c)) % c) * a) % c;
}

이 문제의 핵심 풀이는 long long과 % 남발하기이다.

 

오늘도 진짜 화나부러서 질문 게시판에서 반례를 다 보다가 찾은 명질문과 명답안🎵

진짜 이런 분들이 계셔서 대한민국의 미래가 밝은거다..⭐

https://www.acmicpc.net/board/view/43516

글 읽기 - 범위 값을 넘어가지 않은 것 같은데 대체 무엇이 잘못입니까!

이거 진짜 제 마음입니다 진짜 미쳐부러요

 

 

long long이 문제일거 같았는데 모든걸 다 롱롱해야지만 풀리다니..

아침에 틀렸습니다 보면 진짜 눙물난다

 

개인적으로 이 문제는 두 가지에서 배울 점이 있었다.👻

 

1. 재귀함수 형식으로 호출할 때는 return에 재귀함수 식을 넣어야 한다. 다른 변수를 넣어주면 당연하게도 재귀 함수가 아니다.

2. 큰 수를 다룰 때는 자료형이 중요하다. %와 롱롱은 진짜 잘 써야 틀리지 않는다.(이 부분이 틀리게 되면 디버깅이 어렵다. 보통은 예시로 내가 생각할 수 있는 작은 숫자를 생각하는데, 실제로 문제가 되는 부분은 오버플로우 되는 부분이기 때문이다!!!!)

 

나는 왜 맨날 나의 멍청코드로 고통받아야 하는가 슬퍼하면서 다른 분들의 코드를 보다가 신기한 걸 발견했다.

if(k&1)  << 이걸 찾다가 C++의 유용한 기능들을 찾았다. 

참고로 k&1 : 홀수면 1, 짝수면 0로 if문과 함께 많이 쓰인다.

 

↓ 자세한건 여기서 보십쇼↓

https://www.acmicpc.net/blog/view/106

C++ 유용한 기능들