[백준알고리즘] 1309번: 동물원 -Python

[백준알고리즘] 1309번: 동물원 -Python

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

1309번: 동물원

이 문제는 세가지 경우로 나눠서 생각하면 된다. 현재 2xN크기의 우리가 존재한다고 했을 때 2x1부터 차례대로 늘려가며 생각을 할 것이다. i번째 행을 추가할 때를 생각해보겠다.

 

i번째 행을 추가할 때 i번째 행에 사자를 배치할 수 있는 경우의 수는 3가지이다. 왼쪽과 오른쪽 어느 곳에도 배치하지 않는 것, 왼쪽에 배치하는 것, 오른쪽에 배치하는 것. 이 3가지를 기준으로 생각할 것이다.

 

1. i번째 행에 사자 배치 안 하기

  i번째 행에 사자를 배치 안 하는 경우는 i-1번째에 사자가 어느 곳에 위치해도 상관없다. 즉, i-1번째 행에서 사자가 없을 수도 있고, 왼쪽에 위치할 수도 있고, 오른쪽에 위치할 수도 있다.

 

2. i번째 행에 사자 왼쪽에 배치

  i번째 행에 사자를 왼쪽에 배치하기 때문에 i-1번째 행에는 사자가 왼쪽에 존재할 수 없다. 즉, i-1번째 행에는 사자가 없거나 오른쪽에 위치할 수 있다.

 

3. i번째 행에 사자 오른쪽에 배치

  i번째 행에 사자를 오른쪽에 배치하기 때문에 i-1번째 행에는 사자가 오른쪽에 존재할 수 없다. 즉, i-1번째 행에는 사자가 없거나 왼쪽에 위치할 수 있다.

 

위의 3가지를 토대로 점화식을 만들게 된다면 3개의 리스트를 가지고 아래와 같이 만들 수 있을 것이다.

dp_no[i] = (dp_no[i-1] + dp_left[i-1] + dp_right[i-1]) % mod

dp_left[i] = (dp_no[i-1] + dp_right[i-1]) % mod

dp_right[i] = (dp_no[i-1] + dp_left[i-1]) % mod

 

위 식을 가지고 만든 첫 번째 코드가 아래와 같다.

 

import sys

N = int(sys.stdin.readline())
no_lion, left_lion, right_lion = [0] * (N+1), [0] * (N+1), [0] * (N+1)
mod = 9901

no_lion[0] = 1
for i in range(1, N+1):
    no_lion[i] = (no_lion[i-1] + left_lion[i-1] + right_lion[i-1]) % mod
    left_lion[i] = (no_lion[i-1] + right_lion[i-1]) % mod
    right_lion[i] = (no_lion[i-1] + left_lion[i-1]) % mod

sys.stdout.write(str( (no_lion[N] + left_lion[N] + right_lion[N]) % mod ))

 

사실 위의 코드는 배열이 필요가 없다.

 

아래 코드의 주석처리와 같은 코드를 반복해서 돌려도 되지만 modulo 때문에 코드가 길어져서 아래와 같이 작성했다. left와 right는 항상 양수이고, no의 경우가 항상 크기 때문에 아래와 같이 작성해도 괜찮다. 배열을 생성하지 않아서 초기에 시간 소요가 없으며 메모리도 적게 사용할 수 있다.

import sys

N = int(sys.stdin.readline())
mod = 9901
no, left, right = 1, 0, 0

for i in range(N):
    # no, left, right = no + left + right, no + right, no + left
    no = (no + left + right) % mod
    left, right = no - right, no - left 

sys.stdout.write(str( (no + left + right) % mod ))

 

또 한 가지 방법이 있는데, 이 식은 그냥 푸신 분들이 규칙을 찾아서 풀으신 것 같다. 규칙이 나온 이유를 찾아보려 했는데 나한텐 어렵다 ㅎㅎ.

 

dp[i] = (dp[i-1]*2 + dp[i-2]) %mod

 

잘못된 점이나 부족한 점 지적해주시면 감사하겠습니다