JUNGOL...123

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);
};

 

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)
{
	const static int MODULATION{ 20091024 };

	int modNum{ x % MODULATION };

	long long result{ 1 };
	while (pow-- > 0)
	{
		result = (result * modNum) % MODULATION;
	}

	return result;
}

 

---

실행 결과 Time Limit Exceed(60)

원인 여전히 시간 초과가 걸린다. 뭔가 분할해서 처리해야 할 것 같은데 어떻게 나눠야 할 지 감이 안 온다.

처리 방법 구글링을 통해 분할 방법을 확인해 보고 따라서 구현해 보자.

---

 

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

NadanKim/CodingTest_JUNGOL

 

문제출처

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