[ BOJ / Python ] 1309번 동물원
6896 단어 dynamic programmingDPpythonbojDP
이번 문제는 다이나믹 프로그래밍을 통해 해결하였다. 점화식을 찾는 과정이 정말 오래 걸렸다. 결국은 구글링을 통해 점화식을 찾아 겨우 해결할 수 있었다. 이 문제 점화식의 핵심은 맨 위에 두 칸중 사자가 어디에 있는지에 따라서 따로따로 메모라이제이션을 해야한다는 점이었다.
본인은 dp를 3차원 배열로 만들고 dp[n][0]은 위의 두 칸 중에서 왼쪽에 사자가 있을 경우, dp[n][1]은 위의 두 칸 중에서 오른쪽에 사자가 있을 경우, dp[n][2]는 위의 두 칸 중에서 사자가 어느쪽에도 없을 경우로 설정하였다.
1 2 3 4
dp[i][0] 1 2 5 12
dp[i][1] 1 2 5 12
dp[i][2] 1 3 7 17
위와 같이 dp[i][0]은 dp[i-1][1]+dp[i-1][2]의 값을 가지게 되고, dp[i][1]은 dp[i-1][2]+dp[i-1][0]의 값을 가지게 되고, dp[i][2]는 dp[i-1][0]+dp[i-1][1]+dp[i-1][2]의 값을 가지게 된다.
이 문제에서 n의 값이 커지면 커질 수록 수가 급격하게 커지기 때문에 매 반복마다 dp를 구할 때에 %9901연산을 계속해서 진행해주어야 한다. 이를 안할 경우 메모리 초과 에러가 발생하게 된다.
결과적으로 점화식은
dp[n]=(dp[n-1][0]+dp[n-1][1]) + (dp[n-1][2]+dp[n-1][0]) + (dp[n-1][0]+dp[n-1][1]+dp[n-1][2])
로 구할 수 있다.
- n을 입력받는다.
- dp를 0으로된 3차원 배열을 만든다.
- 3만큼 반복하는 i에 대한 for문을 돌린다.
-> dp[1][i]를 1로 갱신한다. - 2부터 n까지의 i에 대한 for문을 돌린다.
-> dp[i][0]을 (dp[i-1][1]+dp[i-1][2])%9901로 갱신한다.
-> dp[i][1]을 (dp[i-1][2]+dp[i-1][0])%9901으로 갱신한다.
-> dp[i][2]를 (dp[i-1][0]+dp[i-1][1]+dp[i-1][2])%9901로 갱신한다. - dp[n] 배열을 모두 더한 값에 9901을 나눈 나머지를 출력한다.
Code
n=int(input())
dp=[[0]*3 for _ in range(n+1)]
for i in range(3):
dp[1][i]=1
for i in range(2, n+1):
dp[i][0]=(dp[i-1][1]+dp[i-1][2])%9901
dp[i][1]=(dp[i-1][2]+dp[i-1][0])%9901
dp[i][2]=(dp[i-1][0]+dp[i-1][1]+dp[i-1][2])%9901
print(sum(dp[n])%9901)
n=int(input())
dp=[[0]*3 for _ in range(n+1)]
for i in range(3):
dp[1][i]=1
for i in range(2, n+1):
dp[i][0]=(dp[i-1][1]+dp[i-1][2])%9901
dp[i][1]=(dp[i-1][2]+dp[i-1][0])%9901
dp[i][2]=(dp[i-1][0]+dp[i-1][1]+dp[i-1][2])%9901
print(sum(dp[n])%9901)
Author And Source
이 문제에 관하여([ BOJ / Python ] 1309번 동물원), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@xx0hn/BOJ-Python-1309번-동물원저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)