문제
00타일 과 1타일을 붙여서 N이 주어졌을 때 지원이가 만들 수 있는 모든 가짓수를 세시오.
지원이는 N=1일 때 1만 만들 수 있고, N=2일 때 00, 11을 만들 수 있다.(01, 10은 만들 수 없다)
또한 N=4일 때는 0011,0000,1001,1100,1111등 총 5개의 2진 수열을 만들 수 있다.
입력
첫 번째 줄에 자연수 N이 주어진다.(1<=N<=1,000,000) 출력
첫 번째 줄에 지원이가 만들 수 있는 길이가 N인 모든 2진 수열의 개수를 15746으로 나눈 나머지를 출력한다.
이 문제에서 지원이가 길이가 N인 이진 수열을 만들 때.
마지막 타일을 00으로 선택하여 N-1번째와 N번째에 0이 오는 경우와
마지막 타일을 1로 선택하여 N번째에 1이 오는 경우는 교집합이 존재하지 않는 배반사건이므로
지원이가 마지막으로 선택하는 타일에 따라 케이스를 나누어 생각할 수 있다.
dp에서는 배반 사건을 기준으로 케이스를 분류하여 점화식을 세우는 것이 중요하다!
만약 이 문제가 수능 수학 문제로 출제되었을 경우.
이 문제는 가능한 (00타일 개수,1타일 개수)쌍들을 기준으로 케이스 분류 후,
같은 것이 포함된 순열로 경우의 수를 구하는 풀이가 가능한 유형이다.
같.포.순은 동적 계획법(dp)와 관련이 있다!
탑 다운 : 재귀함수+메모제이션
큰 문제를 해결하기 위해 작은 문제를 호출하는 방법
재귀함수로 dp 코드를 작성하는 방식으로 탑 다운 방식에는 메모이제이션이 활용됨
* 메모이제이션 : 한 번 계산된 결과를 메모리 공간에 저장해 두고 다시 호출하는 경우 결과를 가져오는 방식
(메모제이션은 이전 계산을 기록해 놓는다는 넓은 개념으로 dp와는 별도의 개념이다.)
# top-down
n = int(input())
def tile01(n):
if d[n] != 0: return d[n]
d[n] = (tile01(n-1)+tile01(n-2))%15746
return d[n]
d = [0 for _ in range(1000001)]
d[1] = 1; d[2] = 2
print(tile01(n))
바텀 업 : 반복문 + dp 테이블
작은 문제부터 쌓아 나가면서 답을 도출하는 방법
반복문으로 dp 코드를 작성하는 방식으로 dp 테이블이 활용됨
dp의 전형적인 형태는 바텀업 방식이다!
재귀 호출을 하지 않기 때문에 탑 다운 방식에 비해 시간과 메모리 사용량을 줄일 수 있다!!
# bottom-up
n = int(input())
d = [0 for _ in range(1000001)]
d[1] = 1; d[2] = 2
for i in range(3,n+1):
d[i] = (d[i-1]+d[i-2])%15746
print(d[n])
MOD 연산의 분배 법칙
나머지 modulo 연산(%)은 분배법칙이 성립하므로, 두 수 a와 b의 나머지를 구해서 더하는 것과 더한 후 나머지를 구하는 것에 차이가 없다!
그러므로 메모리를 줄이기 위해 나머지를 구한 후 저장해도 됨!
A = q1 x N + r1
B = q2 x N + r2 라고 할 때,
A + B = (q1 + q2) x N + (r1 + r2) 이므로
(A + B) % N = r1 + r2 = A % N + B % N
같은 방식으로 뺄셈, 곱셈도 증명할 수 있다.
(A + B) % N = ((A % N) + (B % N)) % N
(A - B) % N = ((A % N) - (B % N)) % N
(A X B) % N = ((A % N) X (B % N)) % N
나눗셈의 경우 페르마의 소정리를 사용하면 증명할 수 있다고 알려져 있다
(A / B) % N = ((A % N) + (B % N)) / N
풀이
n = int(input())
d = [0 for _ in range(1000001)]
d[1] = 1; d[2] = 2
for i in range(3,n+1):
d[i] = (d[i-1]+d[i-2])%15746
print(d[n])