[알고리즘/백준] 1309번 동물원 Python 파이썬

 

저번 문제는 혼자 힘으로 못 풀어서 글을 못 썼는데 이번 문제는 나름 풀고 성찰할 부분이 있어서 글을 적게 되었습니다. 이번 문제도 DP 문제입니다.

 

 

이번 문제는 2 X N 사자 우리가 주어지고 사자들을 배치할 때의 경우의 수를 9901로 나눈 나머지를 출력하는 문제입니다. 저번에 2133번 문제를 풀었는데 나름 방식이 유사한 문제인거 같습니다. 혹시 해당 문제를 푸셨다면 다음은 2133번을 풀어보는 것을 추천드립니다. 일단 풀이 과정으로는 몇가지의 경우의 수를 직접 그려보았습니다.

 

 

각 경우의 답에서 규칙성을 찾아보았을 때 DP[i] = DP[i-2] + (DP[i-1]*2) 식을 정의할 수 있습니다. 이를 적용해서 코드를 구현하였습니다..

 

다음과 같은 코드로 통과하였습니다..

 

import sys
input = sys.stdin.readline

n = int(input())
dp = [1] * (n+1)
dp[1] = 3

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

print(dp[n])

 

처음에 N =3 의 답을 잘못 세어서 18로 알고 한동안 규칙을 못 찾고 헤맸는 거 같습니다. 규칙성을 찾아서 푸는 문제인만큼 각 경우에 따른 답을 잘 찾는 것도 매우 중요한 거 같습니다.