[백준] 1309 동물원 (파이썬 Python)

https://www.acmicpc.net/problem/1309

1309번: 동물원

문제 설명 

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

 이 동물원에는 사자들이 살고 있는데 사자들을 우리에 가둘 때, 가로로도 세로로도 붙어 있게 배치할 수는 없다. 이 동물원 조련사는 사자들의 배치 문제 때문에 골머리를 앓고 있다.

 동물원 조련사의 머리가 아프지 않도록 우리가 2*N 배열에 사자를 배치하는 경우의 수가 몇 가지인지를 알아내는 프로그램을 작성해 주도록 하자. 사자를 한 마리도 배치하지 않는 경우도 하나의 경우의 수로 친다고 가정한다.

---

풀이 과정

• 나의 풀이

① 이 문제에서 직관적으로 파악한 것은 '분명 N값이 커질수록 전의 결과를 참고해 추가하는 경우의 수를 생각하며 점화식을 세우면 될테니깐... DP문제구나....!'였다.

② 아이디어 열기

(1) 예제 분석하기

 n = 1 ; 3가지

 n = 2 ; 7가지

 n = 3 ; 17가지

 사실상 구하는 과정도 너무 어려웠다....!!! 어려웠던 이유가 기준을 무엇으로 할지 몰랐기 때문이다... 기준을 무엇으로 정할지에 대해 생각하던 도중 ①의 과정에서 DP문제임을 파악했었던 기억이 떠올랐고 전의 결과를 참고해야함을 떠올렸다. 전의 결과를 참고하는 과정에서.... 기준을 무엇으로 해야할까...?

 2x1의 타일을 새로 추가할 때 추가되는 2x1의 타일 기준으로 고려할 것은 2x1의 타일에서 아무것도 선택 안할 수도 있고 왼쪽 타일을 선택할 수도 있고 오른쪽 타일을 선택할 수도 있으므로 총 3가지의 경우로 분류가 가능하다.

 기준대로 분류한다면 위와 같은 점화식을 세울 수 있다.

● 아무것도 선택 안하는 경우 (dp[i][0]이라 하자)

  dp[i][0] = dp[i-1][0] + dp[i-1][1] + dp[i-1][2]

● 왼쪽 타일을 선택하는 경우 (dp[i][1]이라 하자)

  dp[i][1] = dp[i-1][0] + dp[i-1][2]

● 오른쪽 타일을 선택하는 경우 (dp[i][2]라 하자)

  dp[i][2] = dp[i-1][0] + dp[i-1][1]

 

(2) 코드 구현 (첫번째 시도)

# 1309 동물원
import sys
input = sys.stdin.readline
n = int(input())
dp = [0]*(n+1)
for i in range(n+1) :
    dp[i] = [0,0,0]
dp[1][0] = 1
dp[1][1] = 1
dp[1][2] = 1

for i in range(2, n + 1):
    dp[i][0] = dp[i - 1][0] + dp[i - 1][1] + dp[i - 1][2]
    dp[i][1] = dp[i - 1][0] + dp[i - 1][2]
    dp[i][2] = dp[i - 1][0] + dp[i - 1][1]

print(sum(dp[n]) % 9901)

 이차원리스트를 이용하여 dp리스트에 값을 저장해주었다.

 결과는...!!

 메모리 초과로 인한 오답이다 ㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠ....

 

(3) 코드 구현 (두번째 시도)

 무엇이 잘못되었을까...?? 이중 for문을 사용한 것도 아닌데 말이다.. 이럴 때는 항상 문제 조건을 다시 봐야한다..!!

 "첫째 줄에 우리의 크기 N(1≤N≤100,000)이 주어진다." 이 말이 포인트인 것 같다. for문으로 규칙대로 값을 구하던 도중 메모리 초과가 났을 가능성이 크다. 그 이유는 결과값만 9901의 나머지로 출력했지 for문 내의 결과는 9901의 나머지로 표시하지 않았기 때문이다..!!

 이를 해결한 코드는 다음과 같다.

# 1309 동물원
import sys
input = sys.stdin.readline
n = int(input())
dp = [0]*(n+1)
for i in range(n+1) :
    dp[i] = [0,0,0]
dp[1][0] = 1
dp[1][1] = 1
dp[1][2] = 1


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

print(sum(dp[n]) % 9901)

  결과는...!!

 성공이다-!-!-!-!

---

후기

  항상 오류가 났을 땐 처음으로 돌아가자. 메모리 초과는 과정에서도 문제가 발생 가능하군!!!