[멀티잇 코딩테스트 러닝클래스] 다이나믹 프로그래밍(DP) : 피보나치 수, 보드게임, 거리두기 - 파이썬(Python)

피보나치 수

 

 

 

 

 

문제에 나와있듯 피보나치 수는 1항과 2항은 1이고, 3항부터는 전전 항과 이전 항의 합으로 나타낼 수 있습니다. 

 

이에 따라 배열 fibo = [1,1]로 초기화해놓고, 반복문을 통해 K-1번째까지 fibo[i]에 fibo[i-2] + fibo[i-1]를 삽입합니다. 이후 문제 조건에 따라 fibo[K-1]를 10,000,007로 나눈 나머지를 출력하면 되겠습니다.

 

 

K = int(input())
fibo = [1,1]
for i in range(2,K) :
	fibo.append(fibo[i-2] + fibo[i-1])

print(fibo[K-1] % 1000000007)

 

 

---

 

보드게임

 

 

 

 

 

다이나믹 프로그래밍에서는 점화식을 파악해내는 것이 중요합니다.

 

우선 0번 칸부터 1번 칸, 0번 칸부터 2번칸으로 가는 방법은 하나밖에 없습니다.

다음으로 0번 칸부터 3번 칸으로 가는 방법은 1칸씩 3번 이동하는 경우(1-1-1)와 3칸을 한 번에 이동하는 경우 총 2가지입니다.

 

그 다음부터는 아래와 같습니다.

 

 

0번 칸 ~ 4번 칸 : 1-1-1-1  |  1-3  |  3-1
0번 칸 ~ 5번 칸 : 1-1-1-1-1  |  1-1-3  |  1-3-1  |  3-1-1
0번 칸 ~ 6번 칸 : 1-1-1-1-1-1  |  1-1-1-3  |  1-1-3-1  |  1-3-1-1  |  3-1-1-1  |  3-3
0번 칸 ~ 7번 칸 : 1-1-1-1-1-1-1  |  1-1-1-1-3  |  1-1-1-3-1  |  1-1-3-1-1  |  1-3-1-1-1  |  3-1-1-1-1  |  1-3-3  |  3-1-3  |  3-3-1  

 

 

N번 칸까지 이동하는 방법의 수를 나열하면 아래와 같습니다.

 

 

                                1가지   -->  1가지  -->  2가지  -->  3가지  -->  4가지  -->  6가지  -->  9가지

 

 

4항부터 살펴보시죠. 무언가 규칙이 보이시나요? 맞습니다. 바로 3번째 전 항과 이전 항의 합임을 알 수 있습니다. 예를 들어 <9가지>는 3번째 전 항인 <3가지>와 이전 항인 <6가지>의 합이죠.

 

즉, 이를 점화식으로 나타내면 dp[i] = dp[i-1] + dp[i-3]이 됩니다.

 

 

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

for i in range(2,N) :
	if i==2 :
		dp[i] = dp[i-1] + dp[i-2]
	else :
		dp[i] = dp[i-1] + dp[i-3]
		
print(dp[N-1] % 1000000007)

 

 

---

 

거리두기

 

 

 

 

 

 

 

 

점화식을 뽑아내기가 상당히 어려운 문제입니다. 하나씩 차근차근해보겠습니다.

 

우선 N=2, 두 개의 줄이 주어졌다면 스티커를 붙이는 경우는 아래와 같습니다.

 

 

 

 

이를 정리해보면, 아래와 같습니다.

 

i) 맨 윗 줄에 스티커가 없을 때 : 5가지

ii) 맨 윗 줄의 왼쪽에만 스티커가 있을 때 : 3가지

iii) 맨 윗 줄의 중앙에만 스티커가 있을 때 : 4가지

iv) 맨 윗 줄의 오른쪽에만 스티커가 있을 때 : 3가지

v) 맨 윗 줄의 왼쪽과 오른쪽에 스티커가 있을 때 : 2가지

 

그렇다면 N=3, 세 개의 줄이 주어진다면 어떻게 될까요? 제가 정리해 본 바로는 아래와 같습니다. 원활한 이해를 위해 예시를 참고해주세요!

 

ex) [i][i] 칸 : 위의 두 줄에 스티커가 없는 경우

ex) [iii][ii] 칸 : 첫번째 줄의 중앙과 두번째 줄의 왼쪽에 스티커가 있는 경우

 

 

	i	ii	iii	iv	v
i	5	3	4	3	2
ii	5		4	3
iii	5	3		3	2
iv	5	3	4
v	5		4

 

 

위 표를 점화식으로 표현해볼까요? 

 

 

dp[i][0]       =       dp[i-1][0]     +     dp[i-1][1]     +     dp[i-1][2]     +     dp[i-1][3]     +     dp[i-1][4]
dp[i][1]       =       dp[i-1][0]                                +     dp[i-1][2]     +     dp[i-1][3]
dp[i][2]       =       dp[i-1][0]     +     dp[i-1][1]                               +     dp[i-1][3]     +     dp[i-1][4]
dp[i][3]       =       dp[i-1][0]     +     dp[i-1][1]     +     dp[i-1][2]
dp[i][4]       =       dp[i-1][0]                                +     dp[i-1][2]

 

 

단, 코드를 작성할 때 위의 점화식대로 수를 저장하다보면 수가 엄청나게 커지기 때문에 런타임 에러가 발생합니다. 따라서  dp[i]에 수를 저장할 때는 위 점화식에 100,000,007로 나눈 나머지의 값을 저장하도록 합니다.

 

 

N = int(input())
dp = [[0 for x in range(5)] for y in range(100001)]
dp[0][0] = 1
rest = 100000007
result = 5

for i in range(1,N+1) :
		dp[i][0] = (dp[i-1][0] + dp[i-1][1] + dp[i-1][2] + dp[i-1][3] + dp[i-1][4]) % rest
		dp[i][1] = (dp[i-1][0]              + dp[i-1][2] + dp[i-1][3]) % rest
		dp[i][2] = (dp[i-1][0] + dp[i-1][1]              + dp[i-1][3] + dp[i-1][4]) % rest
		dp[i][3] = (dp[i-1][0] + dp[i-1][1] + dp[i-1][2]) % rest
		dp[i][4] = (dp[i-1][0]              + dp[i-1][2]) % rest
	
result = (dp[N][0] + dp[N][1] + dp[N][2] + dp[N][3] + dp[N][4]) % rest
print(result)