백준 1309번(파이썬):동물원
백준 1309번 문제 정리글 입니다.
문제 출처-https://www.acmicpc.net/problem/1309
문제 내용
나의 풀이
N=int(input())
dp=[0]*(N+1)
dp[1]=3
temp=1
for i in range(2,N+1):
A=dp[i-1]
B=dp[i-1]-temp
dp[i]=(A+B+B)%9901
temp=B
print(dp[N])
- 사자를 우리에 가둘 때, 가로 세로로 겹치게 두면 안되기 때문에 한줄씩 추가될 때 각각 3가지 경우로 나눠줬다.
- A=이전 줄이 비어있을 때, B=이전 줄에 하나라도 사자가 있을 때로 나누어 3가지 경우를 각각 더해줬다.
- A는 이전 줄이 비어있어서 이전 dp값을 더해주고, B는 겹치는 경우를 제외하기 위해 이전 dp에서 이전의 B값을 빼고 더해줬다.
나의 풀이 기준으로 B의 경우를 어떻게 계산할지가 중요했던것 같다. 그리고 항상 문제의 조건을 끝까지 읽어봐야한다…(처음에 값을 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)
나의 풀이와 비슷하게 이차원 배열을 이용하여 3가지로 나눠서 해결하였다…
