-
(백준 1629번 곱셈 C++) 라이님 블로그 대회 알고리즘 따라잡기 4) 분할 정복(Divide and Conquer) 3탄PROGRAMMING/알고리즘 2024. 1. 9. 21:23
분할정복이 점점 익숙해져간다! 오늘의 문제는 거듭제곱 문제!
이전 포스팅은 여기에!↓
2024.01.08 - [알고리즘] - (백준 1780번 종이의 개수 C++) 라이님 블로그 대회 알고리즘 따라잡기 4) 분할 정복(Divide and Conquer) 2탄
(백준 1780번 종이의 개수 C++) 라이님 블로그 대회 알고리즘 따라잡기 4) 분할 정복(Divide and Conquer)
후후 이번주도 1일 1알고리즘 가즈아~! 이전 포스팅은 여기에!↓ 2024.01.07 - [알고리즘] - (백준 1992번 쿼드트리 C++) 라이님 블로그 대회 알고리즘 따라잡기 4) 분할 정복(Divide and Conquer) 1탄 (백준 1992
jjo-mathstory.tistory.com
백준 1629번
https://www.acmicpc.net/problem/1629
1629번: 곱셈
첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어진다. A, B, C는 모두 2,147,483,647 이하의 자연수이다.
www.acmicpc.net
우선 문제를 보면 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
글 읽기 - 범위 값을 넘어가지 않은 것 같은데 대체 무엇이 잘못입니까!
댓글을 작성하려면 로그인해야 합니다.
www.acmicpc.net
이거 진짜 제 마음입니다 진짜 미쳐부러요 long long이 문제일거 같았는데 모든걸 다 롱롱해야지만 풀리다니..
아침에 틀렸습니다 보면 진짜 눙물난다 개인적으로 이 문제는 두 가지에서 배울 점이 있었다.👻
1. 재귀함수 형식으로 호출할 때는 return에 재귀함수 식을 넣어야 한다. 다른 변수를 넣어주면 당연하게도 재귀 함수가 아니다.
2. 큰 수를 다룰 때는 자료형이 중요하다. %와 롱롱은 진짜 잘 써야 틀리지 않는다.(이 부분이 틀리게 되면 디버깅이 어렵다. 보통은 예시로 내가 생각할 수 있는 작은 숫자를 생각하는데, 실제로 문제가 되는 부분은 오버플로우 되는 부분이기 때문이다!!!!)
나는 왜 맨날 나의 멍청코드로 고통받아야 하는가 슬퍼하면서 다른 분들의 코드를 보다가 신기한 걸 발견했다.
if(k&1) << 이걸 찾다가 C++의 유용한 기능들을 찾았다.
참고로 k&1 : 홀수면 1, 짝수면 0로 if문과 함께 많이 쓰인다.
↓ 자세한건 여기서 보십쇼↓
https://www.acmicpc.net/blog/view/106
C++ 유용한 기능들
이 글은 유용한 기능들을 소개하는 글입니다. "요약 노트" 정도로 생각해주시면 될 것 같습니다. 그래서 구체적인 원리나 주의사항, 확장 가능성에 대한 이야기는 생략합니다. 의견은 언제든 환
www.acmicpc.net
'PROGRAMMING > 알고리즘' 카테고리의 다른 글