Brute-Force Attack

문제: BRUTEFORCE / 분할정복

[해결책 / 후기]

무척 고생한 문제다. 어떤 사람들은 바로 해결전략이 떠오르겠지만 머리가 별로 안좋은 난..쿨럭~

1. 정답 파악

풀이 방법과 상관없이 정답이 무엇인지 따져본다. 

N=10일 때 한자리 암호를 만드는 방법은 10가지이다. 2자리 암호를 만드는 방법은, 첫 자리에 10가지가 있고 둘 째 자리에도 10자리가 올 수 있으므로 총 100가지가 된다. 그렇다면 이것은 중복순열?

정답인 즉, N+N^(A+1)+N^(A+2) .... N^B 가 된다.

2. 풀이법에 대한 고찰

이제 정답은 알았다. 그런데 풀이법이 만만찮다. 

(1) 일단 본능적으로 pow 함수를 쓰면 된다는 생각이 든다.

pow(N, A)+pow(N, A+1)+pow(N, A+2) ...

더 효율적으로 바꿀 수도 있다. pow 함수를 한번만 호출해두는 것이다.

n = pow(N, A)

n *= n (다음 항은 n^(A+1)이므로 n^A에 n을 곱한 결과가 된다)

그래도 무척이나 오래 걸릴 것같다.

(2) 조금 더 생각해보면 이 식은 등비수열임을 알 수 있다. 그래서 등비수열 합의 공식을 이용하면

a = n^A

sum = a * (n^(B-A+1)-1)/n-1

같이 표현할 수 있다.

속도 개선은 되었지만, 정답을 구할 수 없다. 결과 값이 너무 크기 때문이다.

128^3000 이런 숫자를 어떻게 표현할 것인가? 안타깝게도 컴퓨터에는 저런 어마무시한 수를 저장할 데이터형이 없다.

(3) 이제 눈에 들어오는 것은 1000000007 이라는 숫자다. 왜 저 숫자의 나머지를 출력하라고 했을까?

여기서 초점은 1000000007 이라는 숫자로 나눈 나머지를 구하는데 맞춰진다.

여기에서 알아야할 사실이 있다.

(x+y) mod n = ((x mod n) + (y mod n)) mod n

(x*y) mod n = ((x mod n)*(y mod n)) mod n

이라는 사실이다. 다 더한다음 나머지를 구하거나, 따로 구해서 더하거나.. 같다는 것이다.

이제 어마무시하게 커지는 숫자를 제어할 방법은 알았다. 위의 식으로 100000007을 넘는 수들의 나머지만 다루는 것이다.

여기까지 알고나서도 막히는 부분은 시간을 줄이는 방법이다.

여전히 최악의 경우 1부터 100000000승 까지의 합을 빠르게 계산할 방법이 떠오르지않았다. 

나머지들의 합이므로 등비수열도 써먹을 수가 없다. 

결국 핵심은 

n^A+n^(A+1)+n^(A+2)....n^B

이 식을 어떻게 빨리 푸느냐다. 이제 식을 정리하면 다음과 같다.

편의를 위해 초항으로 식을 묶는다

n^A(1+n+n^2...)  ---------------------- (1)

(1)의 식에서 괄호 안의 수를 구한다. (초항은 나중에 곱해주면 된다)

각 항의 합까지 결과가 어떻게 되는지 살펴보자.

1항까지의 합: 1

2항까지의 합: 1+n

3항까지의 합: 1+n+n^2 = (1+n)+n^2

4항까지의 합: 1+n+n^2+n^3 = (1+n)+n2(1+n) = (1+n)(1+n^2)

5항까지의 합: 1+n+n^2+n^3+n^4 = (1+n)(1+n^2)+n^4

6항까지의 합: 1+n+n^2+n^3+n^4+n^5 = (1+n+n^2)(1+n^3)

...

이렇게 적어보니 규칙이 보이기 시작했다.  6항을보면 두 부분으로 나눌 수 있다. 

(1+n+n^2) 이 부분은 3항까지의 합과 같다. (글자색을 보자)

(1+n^3) 이 부분은 따로 구해야 한다.

이제 n항까지의 합을 구하는 함수를 f라고 하고 n^x를 구하는 함수를 pow라고 하면 다음과 같이 정리된다.

밑수 (base), 승수 (exp)가 주어질 때, 입력되는 exp가 짝수인 경우는 다음과 같다.

f(base, exp/2) * (1+pow(exp/2))

홀수인 경우는 다음과 같이 정리할 수 있다.

f(base, exp-1) + pow(exp-1)

다음 코드는 이 식을 옮겨놓은 것에 불과하다.

코드: https://github.com/xgate/algospot/blob/master/DIV/BRUTEFORCE.cpp

일단 문제를 풀기전에 재귀를 타는 문제라면 식을 먼저 정리하는 습관을 들여야겠다.

[출처] [AOJ 문제] Brute-Force Attack|작성자 DevMoon

[출처] [AOJ 문제] Brute-Force Attack|작성자 DevMoon