[백준] 1309 - 동물원 🦁 (Python) / 실버 1 / DP

BAEKJOON Logo

 

Contents

 

---

1.  문제🔥

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

문제

문제를 요약하자면, 우리의 크기 N이 주어질 때, 우리의 크기에 따라 사자를 배치하는 모든 경우의 수를 9901로 나눈 나머지를 출력합니다.
사자는 가로, 세로로 붙어있게 배치할 수 없고, 사자를 한 마리도 배치하지 않는 경우도 하나의 경우의 수로 포함합니다.

 

1) 예제 입출력❄️

예제 입출력

입력으로 4가 주어지면, 4행, 2열짜리 우리에 사자를 채우는 경우의 수를 출력하면 됩니다.

 

2. 핵심 논리☢️

길이가 3인 리스트를 원소로 갖는 dp를 만들어서 왼쪽배치로 시작하는 경우, 오른쪽 배치로 시작하는 경우, 배치하지 않는 것으로 시작하는 경우에 대해, dp 테이블을 채워서 마지막 원소를 모두 더해서 출력합니다.

 

3. 풀이 코드✅

1) 코드

N = int(input())
dp = [[0,0,0] for _ in range(N)]
dp[0] = [1,1,1]

for i in range(1,N):
    dp[i][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] = sum(dp[i-1])%9901

print(sum(dp[-1])%9901)

우리의 크기 N을 입력받습니다. dp를 [0,0,0]을 N개 갖는 이중 리스트로 초기화하고, 첫 번째 원소를 [1, 1, 1]로 초기화해줍니다. 이 의미는 사자를 왼쪽에 넣는 경우, 오른쪽에 넣는 경우, 안 넣는 경우에 대한 카운트를 각각 세주겠다는 의미입니다. for문을 반복하며 왼쪽, 오른쪽, 안 넣는 경우의 카운트를 각각 9901로 나눠 갱신합니다. 왼쪽의 경우는 전에 오른쪽에 채운 경우와 안채운 경우를 합한 경우의 수로 갱신해줍니다. 오른쪽도 비슷한 맥락입니다. 안채운 경우는 사자가 붙어있는 경우가 없기 때문에 sum(dp[i-1])%9901을 해줍니다. 여기서 9901로 나눠주는 이유는 dp에 들어가는 숫자가 너무 커지기 때문에 미리 9901로 나눠두는 것입니다. 이는 다음과 같은 나머지 분배 법칙 덕분에 적용 가능합니다.

나머지 분배법칙
(A+B)% p = [(A% p) + (B% p)] % p

그리고 결과도 9901로 나눠줘서 출력해주면 됩니다.

2) 주석 달린 코드

N=int(input())
## dp 테이블 초기화
dp = [[0,0,0] for _ in range(N)]
dp[0]=[1,1,1] # 왼쪽 채운 경우, 오른쪽 채운 경우, 안채운 경우

for i in range(1,N):
    dp[i][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] = sum(dp[i-1])%9901 # 안채우는 경우

print(sum(dp[-1])%9901)

 

 

읽어주셔서 감사합니다.

다음에 더욱 유익한 글로 찾아오겠습니다.

 

* 관련 풀이 코드는 아래 깃허브 링크에 있습니다.

https://github.com/netsus/BaekJoon/blob/master/jupyter/1309_%EB%8F%99%EB%AC%BC%EC%9B%90.ipynb

GitHub - netsus/BaekJoon: Algorithm Problem solving

Reference)
1. BAEKJOON Logo: https://www.acmicpc.net/