[백준 1904번] 결과값으로 큰 정수의 나머지를 원하는 경우

01타일(#1904)

• Problem

지원이에게 2진 수열을 가르쳐 주기 위해, 지원이 아버지는 그에게 타일들을 선물해주셨다. 그리고 이 각각의 타일들은 0 또는 1이 쓰여 있는 낱장의 타일들이다. 어느 날 짓궂은 동주가 지원이의 공부를 방해하기 위해 0이 쓰여진 낱장의 타일들을 붙여서 한 쌍으로 이루어진 00 타일들을 만들었다. 결국 현재 1 하나만으로 이루어진 타일 또는 0타일을 두 개 붙인 한 쌍의 00타일들만이 남게 되었다. 그러므로 지원이는 타일로 더 이상 크기가 N인 모든 2진 수열을 만들 수 없게 되었다. 예를 들어, N=1일 때 1만 만들 수 있고, N=2일 때는 00, 11을 만들 수 있다. (01, 10은 만들 수 없게 되었다.) 또한 N=4일 때는 0011, 0000, 1001, 1100, 1111 등 총 5개의 2진 수열을 만들 수 있다. 우리의 목표는 N이 주어졌을 때 지원이가 만들 수 있는 모든 가짓수를 세는 것이다. 단 타일들은 무한히 많은 것으로 가정하자.

 

• Hint

Bottom up 방식과 왜 정수를 나누라고 하는지 생각해보자.

 

• Solution

Bottom up 과 메모리 초과를 고려한 풀이 [ 정답 ]

n = int(input())
res = [0]*1000001
res[0] = 1
res[1] = 1
for i in range(2, n+1):
    res[i] = res[i-1]+res[i-2]
    res[i] = res[i] % 15746
print(res[n])

 
1. 식의 점화식을 구해서 각각 구하는 방식이 아닌 피보나치 수열 이라는 규칙 찾기

간단히 위와 같이 조금 써본 후에 개수를 카운트 해서 피보나치가 아닌가? 생각을 하여 피보나치라고 가정하고 푸는 방법도 있지만 맨 아래 5자리 수를 구해내기 위에서 3자리 수에서 00 을 추가하는 경우와 4자리 수에서 1을 추가하는 경우로 나누어 생각해보면 쉽게 피보나치인 사실을 확인 할 수 있다.

 

---

처음 풀이

 

2-1. Top up 방식 ( 재귀 + 동적할당 ) 과 나머지 값에 대해서 마지막에 적용해준 방법 [ 재귀 최대값 오류 ]

def jiwon(n):
    if res[n] != 0:
        return res[n]
    else:
        res[n] = jiwon(n-1) + jiwon(n-2)
        return res[n]


n = int(input())
res = [0]*1000001
res[0] = 1
res[1] = 1

print(int(jiwon(n) % int(15476)))

위의 큰수부터 재귀를 하듯이 내려오게 되면 아무리 동적할당을 통해서 각 파트 별로 수가 저장되어 복잡도는 크지 않지만 최대 1000000 번이 들어가게 되면 일반적인 (recursion limit를 증가 시키지 않은) 상황에서는 최대값이 할당 되었을 경우 

런타임 에러 (RecursionError)가 뜨게 된다.

 

---

두번째 풀이

 

2-2. Bottom up 방식 과 나머지 값에 대해서 마지막에 적용해준 방법 [ 메모리 초과 오류 ]

n = int(input())
res = [0]*1000001
res[0] = 1
res[1] = 1
for i in range(2, n+1):
    res[i] = res[i-1]+res[i-2]
print(res[n] % 15746)

Bottom up 방식을 이용해 재귀 횟수 초과에 대해서는 해결을 하였지만 구해진 값의 최종값에 정수를 나누어 준 나머지를 구하는 수식을 넣었다.

 

이러한 방법이 에러가 형성 되는 이유는 높은 정수 n이 할당된 피보나치 수열 결과값이 자리수가 커져서 이를 저장하고 불러오는데에 메모리가 부족하여 초과가 뜨게된다.

 

따라서 피보나치 수열은 정수합으로만 이루어져있기 때문에 결과값 자체에 나누어 주어도 결과값이 변화하지는 않기 때문에 저장시에 15476을 나누어 나머지를 구한 값을 저장해주면 해결된다.

 

2-3 .  Bottom up 방식 과 나머지를 결과값에 적용시켜 구한 방법 [ 정답 ]

n = int(input())
res = [0]*1000001
res[0] = 1
res[1] = 1
for i in range(2, n+1):
    res[i] = res[i-1]+res[i-2]
    res[i] = res[i] % 15746
print(res[n])