[동적계획법/DP] 백준 1309 동물원 - 파이썬(Python)

 

[ Contents ]

 

 

1. 문제 (링크 참조)

1309번: 동물원

 

 

 

2. 문제 풀이

 2 * N 칸인 동물원에 사자가 배치될 수 있는 모든 경우의 수를 구하는 문제입니다. 사자는 '가로와 세로'로 붙어있을 수 없습니다.

 

2022.02.12 - [Algorithm] - [Algorithm] 메모해두고 불러와서 사용하는 동적 프로그래밍(DP)

[Algorithm] 메모해두고 불러와서 사용하는 동적 프로그래밍(DP)

 이전 선택에 따라 이후 선택이 영향을 받으므로 '그리디 알고리즘'은 사용할 수 없고, 이전 칸의 부분 해를 여러 번 호출해야 하므로 분할정복으로도 풀 수 없습니다. 이 문제는 이전 문제의 해를 기억해두고 불러와서 사용해야 하는 'DP'문제입니다.

 

어흥

어흥

 이전 칸의 상태에 따라 다음 칸이 결정됩니다. 사자들은 가로로 붙어있을 수 없으므로, 위와 같이 3가지로 축약됩니다. '왼쪽만 사자가 있는 경우', '오른쪽만 사자가 있는 경우', '양쪽 다 사자가 없는 경우'.

 

 

1) '현재 칸에 왼쪽만 사자' = '이전 칸에 모두 사자 없음' + '이전 칸에 오른쪽만 사자'
2) '현재 칸에 오른쪽만 사자' = '이전 칸에 모두 사자 없음' + '이전 칸에 왼쪽만 사자'
3) '현재 칸에 양쪽 모두 사자 없음' = '이전 칸에 모두 사자 없음' + '이전 칸에 왼쪽만 사자' + 이전 칸에 오른쪽만 사자'

 이를 점화식으로 나타내면 위와 같습니다.

 

 

 

3. 코드

import sys
input = sys.stdin.readline

# 입력
N = int(input())

# DP
cache = [[0]*3 for _ in range(N)]
cache[0] = [1, 1, 1]

for i in range(1, N):
    cache[i][0] = (cache[i-1][2] + cache[i-1][1]) % 9901  # 왼쪽만 사자
    cache[i][1] = (cache[i-1][2] + cache[i-1][0]) % 9901  # 오른쪽만 사자
    cache[i][2] = (cache[i-1][0] + cache[i-1][1] + cache[i-1][2]) % 9901  # 모두 없음

print(sum(cache[N-1]) % 9901)

 cache[0]는 왼쪽만 사자가 있는 경우, cache[1]는 오른쪽만 사자가 있는 경우, cache[2]는 양쪽 모두 사자가 없는 경우를 나타냅니다. 앞서 살펴본 점화식을 코드로 구현합니다.

 

 

 

import sys
input = sys.stdin.readline

# 입력
N = int(input())

# DP
cache = [[1], [1], [1]]

for i in range(1, N):
    cache[0].append((cache[2][i-1] + cache[1][i-1]) % 9901)  # 왼쪽만 사자
    cache[1].append((cache[2][i-1] + cache[0][i-1]) % 9901)  # 오른쪽만 사자
    cache[2].append((cache[0][i-1] + cache[1][i-1] + cache[2][i-1]) % 9901)  # 모두 없음

print((cache[0][N-1] + cache[1][N-1] + cache[2][N-1]) % 9901)

 미리 리스트를 생성해두지 않고, append 함수로 이어 붙여나갈 수도 있습니다. 이 경우에는 N의 크기에 따라 메모리를 딱 맞게 사용할 수 있습니다.

 

 

 물론 시간도 절약됩니다. Python3과 PyPy3에서 모두 향상된 결과가 나왔습니다.

 저는 C -> C++ -> Java -> Python 순으로 언어를 배워서, 아직도 미리 cache를 생성해두고 대입하는 방식이 익숙합니다. 하지만 Python에서는 append를 이용한 방식을 사용할 수 있으므로, 되도록 이 방향으로 짜 봐야겠습니다..