[BOJ][⚪1][백준#01309] 동물원

문제 출처

BAEKJOON Online Judge #1309

문제

어떤 동물원에 가로로 두칸 세로로 N칸인 아래와 같은 우리가 있다.

이 동물원에는 사자들이 살고 있는데 사자들을 우리에 가둘 때, 가로로도 세로로도 붙어 있게 배치할 수는 없다. 이 동물원 조련사는 사자들의 배치 문제 때문에 골머리를 앓고 있다. 동물원 조련사의 머리가 아프지 않도록 우리가 2*N 배열에 사자를 배치하는 경우의 수가 몇 가지인지를 알아내는 프로그램을 작성해 주도록 하자. 사자를 한 마리도 배치하지 않는 경우도 하나의 경우의 수로 친다고 가정한다.

입력

첫째 줄에 우리의 크기 N(1≤N≤100,000)이 주어진다.

출력

첫째 줄에 사자를 배치하는 경우의 수를 9901로 나눈 나머지를 출력하여라.

예제

입력

4

출력

41

My Sol

N = int(input())
a, b = 3, 2
while N > 1:
    c = a
    a += b*2
    b += c
    a = a%9901 if a > 9901 else a
    b = b%9901 if b > 9901 else b
    N -= 1
print(a)

점화식을 구하고 DP 방식으로 풀어보려니까 메모리가 너무 낭비될 것 같아 변수에 값을 바꿔가며 저장했다.

결과

맞았습니다!!

모범답안

출처 : 원우형

N = int(input())

dp = [0 for i in range(N+1)]
dp[0] = 1
dp[1] = 3
for i in range(2, N+1):
    dp[i] = (dp[i-2] + 2 * dp[i-1]) % 9901

print(dp[N])

동기형이 진짜 dp방식으로 푼 것 풀이이다. dp는 점화식을 구하는 게 다라고 하는데, 왜 이 문제를 헤맸는지 모를 정도로 단순하게 풀어냈다.