정수론 - 합과 곱은 왜 계속 나눠도 문제가 없는가? -

1. 문제

 

https://www.acmicpc.net/problem/1904

1904번: 01타일

 

00과 1을 이용해서 만들 수 있는 길이 n의 이진수열의 개수를 15746으로 나눈 나머지를 구하는 문제

 

 

2. 풀이

 

가능한 경우의 수를 나열해서 규칙을 찾으면 간단해진다

 

 

1,2,3,5,8,...로 이어져서 피보나치 수열이라는 느낌이 온다

 

그래서 한번 해보면

 

from sys import stdin

n = int(stdin.readline())

dp = [0] * 1000001

dp[1] = 1
dp[2] = 2

for i in range(3,n+1):
    
    dp[i] = (dp[i-1]+dp[i-2])

print(dp[n] % 15746)

 

이렇게 하면 시간초과난다

 

그래서 피보나치 수열의 일반항까지 생각해서

 

 

 

 

이 문제는 초항이 달라서 위 일반항과 완전히 같은건 아닌데..

 

아무튼 중요한건 1+sqrt(5)의 n제곱을 구해야하는데 이게 n이 너무 커지면 float error가 난다는게 문제다

 

 

3. 정수론 - 왜 n으로 나눈 나머지를 저장해도 문제가 없을까? -

 

근데 문제에서 15746으로 나눈 나머지를 구하라고 했잖아

 

이미 페르마의 소정리를 공부하면서 정수론의 놀라운 성질을 배운적이 있다

 

#############################

" a를 n으로 나눈 나머지와 b를 n으로 나눈 나머지의 합을 n으로 나눈 나머지는 a+b를 n으로 나눈 나머지와 같다 "

 

$$ ( (a mod n) + (b mod n) ) mod n = (a+b) mod n $$

 

" a를 n으로 나눈 나머지와 b를 n으로 나눈 나머지의 곱을 n으로 나눈 나머지는 a*b를 n으로 나눈 나머지와 같다 "

 

$$ ( (a mod n) * (b mod n) ) mod n = (a*b) mod n $$

############################

 

############################

 

+추가

 

a를 n으로 나눈 나머지는 0~n-1이므로, a를 n으로 나눈 나머지를 다시 n으로 나눈 나머지는 당연히 a를 n으로 나눈 나머지와 같다.

 

(a mod n) mod n = a mod n

 

#############################

 

근데 dp에 피보나치 수를 n으로 나눈 나머지를 저장해놓아도 이게 규칙이 유지되는게 맞냐??

 

이렇게 의심할 수 있지만 실제로 위 성질을 적용해보면 전혀 문제가 없다

 

------------------------------------------------------------------------------------

 

그러면 a[n]이 피보나치 수열이고

 

dp[i] = i번째 피보나치 수를 15746으로 나눈 나머지 = (a[i] mod 15746)라고 정의하자.

 

편의상 m=15746이라고 생각하자.

 

(a[1] mod m + a[2] mod m) 과 a[3](=a[1]+a[2])은 서로 m에 대해 합동이므로

 

dp[3] = a[3] mod m = (a[3] mod m) mod m= (a[1] mod m + a[2] mod m) mod m = (dp[1] + dp[2]) mod m으로 저장해놓으면

 

a[3]을 m=15746으로 나눈 나머지는 dp[3]을 부르면 그만이다

 

비슷하게 a[4](=a[2]+a[3])와 (a[2] mod m + a[3] mod m)이 합동이니까

 

dp[4] = a[4] mod m = (a[4] mod m) mod m = (a[3] mod m + a[2] mod m) mod m = (dp[3] + dp[2]) mod m

 

그래서 a[4]를 m = 15746으로 나눈 나머지는 dp[4]를 부르면 그만이다.

 

 

비슷하게 dp[5] = a[5] mod m = (a[5] mod m) mod m = (a[4] mod m + a[3] mod m ) mod m 

 

= (dp[4] + dp[3]) mod m

 

....

 

일반적으로

 

dp[n] = a[n] mod m = (a[n] mod m) mod m = (a[n-1] mod m + a[n-2] mod m ) mod m

 

= (dp[n-1] + dp[n-2]) mod m

 

이런식으로 피보나치 수열을 m으로 나눈 나머지를 dp에 저장해놓아도 피보나치 수열이 깨진다거나 그런 문제가 없다

 

 

아무튼 그러므로, 피보나치 수열은 n이 커질수록 상당히 커지는데 n = 30만 되어도 엄청 커지던가..?

 

수가 너무 커지면 연산 속도가 그만큼 느려진다

 

그래서 나눈 나머지를 계속 저장해서 숫자를 줄여나가는 전략을 취한다

 

from sys import stdin

n = int(stdin.readline())

dp = [0] * 1000001

dp[1] = 1
dp[2] = 2

for i in range(3,n+1):
    
    dp[i] = (dp[i-1]+dp[i-2]) % 15746

print(dp[n])

 

 

4. 되돌아보기

 

직관적으로만 그냥 나눈거 저장해야지라고 생각했는데

 

정확하게 다시 생각해봤으니까 나중엔 잘 적용할 수 있겠지??

 

피보나치 수열(덧셈), 팩토리얼(곱셈),...

 

 

5. 연습문제

 

https://www.acmicpc.net/problem/15988

15988번: 1, 2, 3 더하기 3

 

6. 풀이

 

이미 푼 문제인데

 

dp[1] = 1

dp[2] = 2

dp[3] = 4

dp[n] = dp[n-1]+dp[n-2]+dp[n-3]

 

의 규칙이 있음은 밝혔다

 

그런데 제한 조건의 수가 너무 커서

 

" a를 n으로 나눈 나머지와 b를 n으로 나눈 나머지의 합을 n으로 나눈 나머지는 a+b를 n으로 나눈 나머지와 같다 "

 

원리를 이용해서 나머지를 dp에 계속 저장하면 된다

 

from sys import stdin

T = int(stdin.readline())

div = 1000000009

dp = [0]*1000001

dp[1] = 1
dp[2] = 2
dp[3] = 4

for i in range(4,1000001):
    
    dp[i] = (dp[i-1]+dp[i-2]+dp[i-3]) % div

for _ in range(T):
    
    n = int(stdin.readline())
    
    print(dp[n])