BOJ 1009 - 분산처리

boj

문제는 간단하지만 타입의 범위와 알고리즘 고민으로 학습하기 좋은 예제 였다.

먼저 보통 사용하던 메서드들로 테스트

	@ParameterizedTest
	@MethodSource("providerParam")
	void test1(int a, int b, int expect) {
		double total = Math.pow(a, b);
		int actual = Math.floorMod((long)total, 10);

		assertEquals(expect, actual);
	}

• 결과
  • 7100 큰 값이 되면서 에러 발생
    

• 단순하게, 큰 값은! BigInteger
  • 테스트는 통과 했지만, 제출하면 메모리 초과 🤣

	@ParameterizedTest
	@MethodSource("providerParam")
	void test2(int a, int b, int expect) {
		BigInteger base = new 	BigInteger(String.valueOf(a));

		BigInteger total = base.pow(b);
		BigInteger actual = total.mod(BigInteger.TEN);

		assertEquals(expect, actual.intValue());
	}

• 메모리를 사용하지 않고 계산 ?
  31 = 3 X 1 = 3 % 10 = 3
  32 = 3 X 3 = 9 % 10 = 9
  33 = 9 X 3 = 27 % 10 = 7
  34 = 27 X 3 = 81 % 10 = 1
  • 34 을 33 결과값 7에 3을 곱하고 mod 값은 1로 동일
    • 7 X 3 % 10 = 1
  • 이쯤되면 반복되는지 한 번 더 봐본다.
    35 = 81 X 3 = 243 % 10 = 3
    36 = 243 X 3 = 729 % 10 = 9
    37 = 729 X 3 = 2187 % 10 = 7
  
  
• 결론

	int result = 1;
	for (int i = 0; i < b; i++) {
    		result = a * result % 10;
    	}
	if (result == 0) {
    		result = 10;
    	}