문제
어떤 동물원에 가로로 두칸 세로로 N칸인 아래와 같은 우리가 있다.
이 동물원에는 사자들이 살고 있는데 사자들을 우리에 가둘 때, 가로로도 세로로도 붙어 있게 배치할 수는 없다. 이 동물원 조련사는 사자들의 배치 문제 때문에 골머리를 앓고 있다.
동물원 조련사의 머리가 아프지 않도록 우리가 2*N 배열에 사자를 배치하는 경우의 수가 몇 가지인지를 알아내는 프로그램을 작성해 주도록 하자. 사자를 한 마리도 배치하지 않는 경우도 하나의 경우의 수로 친다고 가정한다.
입력
첫째 줄에 우리의 크기 N(1≤N≤100,000)이 주어진다.
출력
첫째 줄에 사자를 배치하는 경우의 수를 9901로 나눈 나머지를 출력하여라.
예제 입력 1
4예제 출력 1
41문제
쉽게 말하자면 사자우리에 사자를 겹치지 않게 배치하는 문제
이 문제의 핵심은 사자우리가 늘어남에 따라 배치 경우의 수가 어떻게 증가하는지 규칙성을 찾으면 되는 문제이다.
N이 하나가 추가될 때 어떻게 변하는가??
사자를 배치하는 행위 자체는 독립시행이므로 영향을 주지 않는다.필자는 새로 추가될 때 사자를 배치하는 경우와 배치하지 않는 경우를 분리해서 생각해보았다.
N=1
사자를 넣지 않는경우 1가지
사자를 넣는 경우 2가지
총 3가지
N=2
우리에 사자를 넣는 경우를 노란색, 넣지 않는 경우를 보라색이라고 표시하였다.
사자를 넣지 않는 경우의 수는 총 3가지가 있다.
사자를 놓는 경우의 수는 총 4가지이다.
총 7가지
N이 2에서 3으로 변할 때
사자를 넣지 않는 경우의 수는 7가지가 있다.
사자를 넣는 경우의 수는 10가지가 있다.
총 17가지
즉, 여기서 규칙을 찾을 수 있었다.
N번째 우리에 사자를 넣을 때 N-1번째 경우의 수*2 + N-2번째 경우의 수를 만족한다는 것을 찾았다.
이제 이것을 코드로 구현했다.
1차
#1309
import sys
N = int(sys.stdin.readline())
dp = [0, 3, 7]
for i in range(3, N+1):
dp.append(((dp[i-1] * 2)+ dp[i-2]))
print(dp[N] % 9901)처음에 9901 계산을 마지막에 했더니 메모리 초과가 났다.
따라서, dp배열에 추가시 바로 9901을 나누는 작업을 해야하나?라고 생각했고 그렇게 계산한 결과
2차
#1309
import sys
N = int(sys.stdin.readline())
dp = [0, 3, 7]
for i in range(3, N+1):
dp.append(((dp[i-1] * 2)+ dp[i-2])% 9901)
print(dp[N])
2차때는 메모리 초과없이 문제 풀이에 성공했다.
