백준 1309 파이썬

1309번: 동물원

n  = 1 : 3가지

n = 2 : 7가지

n = 3: 17가지

.,,

어떤 규칙이 있을까 아무리 생각해도 떠오르지 않았다. 기준을 무엇으로 두어야할까? 가 문제였다.

dp는 전의 결과를 참고하는 과정에서 차곡차곡 답이 쌓인다. 이걸 꼭 명심하자.

2x1 타일을 새로 추가할 때 그 때 2x1 타일을 기준으로 총 3가지의 경우로 분류할 수 있다.

1. 아무것도 선택 안할 때 2. 왼쪽 타일 선택 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]

위와 같이 점화식을 세울 수 있다.

그렇다면 i가 n까지 가는 동안 차곡차곡 경우의 수가 쌓인다.

코드

n = int(input())
limit = 100001
dp = [[0] * 3 for _ in range(limit) ]

dp[1][0] = 1
dp[1][1] = 1
dp[1][2] = 1

for i in range(2, limit):
    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)

 

참고자료

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