[Algorithm] 백준 알고리즘 - 1309

문제(1309번)

문제 바로가기

어떤 동물원에 가로로 두칸 세로로 N칸인 우리가 있다.

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

내가 푼 답

n = int(input())

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

고찰

1. 경우의 수를 구하는 것을 보고 조합을 사용할까 생각을 하였지만 문제의 크기가 100,000인 것을 보고 조합은 시간이 걸릴 거 같아서 넘어갔다.
2. 문제에서 경우의 수와 우리의 크기가 일정하게 늘어나는 것을 보고 다이나믹 프로그래밍(dp)를 사용해야한다는 것을 생각했고 점화식을 구해야겠다는 생각을 하였다.
3. 점화식을 구하기 위해 n번째의 경우를 생각하였다. n번째의 경우는 n번째가 채워지지 않는 경우의 수와 n번째가 채워진 경우의 수를 구하면 된다고 생각 하였다.
4. 근데 전자의 경우는 n-1번째의 수를 구하는 것과 같으므로 dp[i-1]이다.
5. 후자의 경우는 2가지로 나뉘는데 첫번째는 n-1이 공백인 경우이다. 이때는 n번째의 경우에 왼쪽 오른쪽 2가지를 가질수 있다. 두번째는 n이 존재할 경우 인데 이때는 n번째의 경우는 정해져 있다.
6. 첫번째의 경우를 구하면 n-1이 공백이라는 말은 즉 n-2번째의 값과 같다는 것이다. 그러므로 이 경우는 dp[i-2]*2이다. 2를 곱하는 이유는 경우의 수가 2개이기 때문이다.
7. 두번째의 경우는 n-1이 채워져있어야 한다. 이 말은 n-1번째의 경우에서 n-1번째의 우리가 존재해야한다. 이 의미는 dp[i-1] - dp[i-2]가 된다. 왜나햐면 dp[i-1]에서 n-1번째에 우리가 존재하지 않을 경우가 dp[i-2]이기 때문이다. 이 경우는 경우의 수가 1개밖에 안되므로 곱하기 2는 안해야된다.
8. 이것을 식으로 표현하면 다음과 같다. dp[i] = dp[i-1] + (dp[i-2]*2) + dp[i-1] - dp[i-2]
9. 식을 정리하면 다음과 같다. dp[i] = dp[i-1]*2 + dp[i-2]
10. 그 후 문제를 제출할 때 print문에서 9901을 나누면 메모리 초과가 뜬다. 이 부분을 조심해야되겠다.