글 읽기 - 곱셈문제 입니다..

khj2804 8년 전 2

일단 해당 문제의 핵심은, 계산 횟수를 줄여야 한다는 것 까지는 알아냈습니다.

그래서 제곱 계산을 2 제곱 끼리 처리하며, 재귀로 묶어 연산 횟수를 줄이면서

동시에 C의 값 ( 코드 내에선 division )을 매번 나누면서 프로그래밍을 돌렸는데

어디에 제가 또 빠트린 부분이 있는가 싶어서 모르겠네요.. 힝..

B의 값이 0이거나 1이 되는 작은 값의 경우도 재귀의 조건에 달아두었는데, 추가적으로 체크해야하는 부분이 또 있을까요?

#include<iostream>
using namespace std;

unsigned int cadition(unsigned int, const unsigned int, const unsigned int);

int main() {
	unsigned int input, count, division, result;

	// input data
	cin >> input >> count >> division;
	
	result = cadition(input, count, division);

	// print
	cout << result;
}

unsigned int cadition(unsigned int input, const unsigned int count, const unsigned int division) {
	if (count == 0) { return 1; }
	
	if ((count % 2) == 0) { return cadition(input * input, count / 2, division) % division; }
	else { return input * cadition(input * input, (count - 1) / 2, division) % division;}
}

yukariko 8년 전 0

중간 계산과정에서 unsigned int범위를 초과할 수 있기때문에

Long long 자료형을 사용하시길 바랍니다.

khj2804 8년 전 0

long long 자료형을 사용해보았지만, 결과의 차이는 없었습니다 ㅠ

yukariko 8년 전 1

input * input 은 division이 이루어 지지 않았기때문에 long long으로도 오버플로우가 발생합니다.

khj2804 8년 전 0

정말 감사합니다! 그 부분까지는 미처 생각을 못했네요!

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

곱셈문제 입니다..

khj2804 8년 전 2

yukariko 8년 전 0

khj2804 8년 전 0

yukariko 8년 전 1

khj2804 8년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말