JUNGOL...122

Intermediate_Coder/분할정복/제곱수 출력

---

문제                                            

X를 Y번 곱한 값을 찾는 프로그램을 작성하라.

결과가 클 수 있기 때문에 결과 값은 20091024로 나눈 나머지를 출력하라.

 

입력 형식                                     

입력의 첫 번째 줄에는 X와 Y가 입력된다.

X와 Y는 모두 0 이상 231-1 이하의 정수이다.

 

출력 형식                                     

X를 Y번 곱한 값을 20091024로 나눈 나머지를 출력하라.

단, 0를 0번 곱한것은 편의상 1로 정한다.

 

입력 예                                        

2 10

 

출력 예                                        

1024

---

PrintSquare.h

#include <iostream>

class PrintSquare : public Base
{
private:
	long long PrintSquareModuler(long long x, long long pow, long long result = 1);
};

 

PrintSquare.cpp

void PrintSquare::Code()
{
	long long x, y;
	std::cin >> x >> y;

	std::cout << PrintSquareModuler(x, y);
}

/// <summary>
/// 주어진 값의 제곱수를 20091024로 나눈 나머지를 반환한다.
/// </summary>
/// <param name="x">곱할 값</param>
/// <param name="pow">곱해지는 횟수</param>
/// <returns>제곱수를 20091024로 나눈 나머지</returns>
long long PrintSquare::PrintSquareModuler(long long x, long long pow, long long result)
{
	const static int MODULATION{ 20091024 };

	if (pow == 0)
	{
		return result;
	}

	int modNum{ x % MODULATION };
	return PrintSquareModuler(x, pow - 1, (result * modNum) % MODULATION);
}

 

---

실행 결과 Time Limit Exceed(60)

원인 이번 경우엔 입, 출력도 많지 않기에 알고리즘 자체를 조금 수정해야 할 것 같다.

처리 방법 재귀적 처리가 아닌 반복문으로 변경해 봐야겠다.

---

 

NadanKim/CodingTest_JUNGOL: JUNGOL 코딩 테스트를 위한 저장소 (github.com)

NadanKim/CodingTest_JUNGOL

 

문제출처

Intermediate_Coder/분할정복/제곱수 출력-JUNGOL