[12849] 본대 산책 In python

> Dp

 

처음에 떠올렸던 알고리즘은 dfs였다.

그런데 dp로 풀게 되면,, 조건을 처리해주는 부분이 매우 까다로울 것 같아서

힌트를 봣더니 

역시나 틀린 방법을 .. ㅎ

 

 

이 문제는 다이나믹 프로그래밍 기법을 이용하여 풀어야한다.

 

D분 후 위치해있어야하는 곳은 정보과학관이다.

 

초기값은 

	정보과학관	전산관	미래관	신양관	한경직기념관	진리관	형남공학관	학생회관
초기값 (0분)	1	0	0	0	0	0	0	0

 

1분 후

정보과학관에서 전산관으로 가는 방법은 1가지

정보과학관에서 미래관으로 가는 방법은 1가지

	정보과학관	전산관	미래관	신양관	한경직기념관	진리관	형남공학관	학생회관
초기값 (0분)	1	0	0	0	0	0	0	0
1분 후	0	1	1	0	0	0	0	0

 

2분 후

	정보과학관	전산관	미래관	신양관	한경직기념관	진리관	형남공학관	학생회관
초기값 (0분)	1	0	0	0	0	0	0	0
1분 후	0	1	1	0	0	0	0	0
2분 후	1+1 = 2	0+0+1= 1	0+1+0=1	1+1+0+0=2	1+0+0+0=1	0	0	0

 

3분 후

	정보과학관	전산관	미래관	신양관	한경직기념관	진리관	형남공학관	학생회관
초기값 (0분)	1	0	0	0	0	0	0	0
1분 후	0	1	1	0	0	0	0	0
2분 후	1+1 = 2	0+0+1= 1	0+1+0=1	1+1+0+0=2	1+0+0+0=1	0	0	0
3분 후	1+1= 2	2+1+2=5	2+1+2+1=6	1+1+1+0=3	1+2+0+0=3	2+1+0=3	1+0=1	0

 

위 같이 구하면 된다.

정보 과학관으로 가는 경우의 수 = 정보 과학관과 연결된 건물로 가는 경우의 수의 합계!

 

여기서 주의할 것은

이동하기 전 배열에다가 더하는 것이 아니라

초기화된 Temp 배열에다가 경우의 수를 더한 뒤

array 배열에 해당 Temp 배열값을 덮어쓰기 해야함.

 

d = int(input())
array = [1, 0, 0, 0, 0, 0, 0, 0]


def move(node):
    # 0 : 정보과학관
    # 1 : 전산관
    # 2 : 미래관
    # 3 : 신양관
    # 4 : 한경직기념관
    # 5 : 진리관
    # 6 : 형남공학관
    # 7 : 학생회관
    temp = [0 for _ in range(8)]
    temp[0] = array[1] + array[2]
    temp[1] = array[0] + array[2] + array[3]
    temp[2] = array[0] + array[1] + array[3] + array[4]
    temp[3] = array[1] + array[2] + array[4] + array[5]
    temp[4] = array[2] + array[3] + array[5] + array[6]
    temp[5] = array[3] + array[4] + array[7]
    temp[6] = array[4] + array[7]
    temp[7] = array[5] + array[6]

    for i in range(8):
        temp[i] = temp[i] % 1000000007
    return temp


for i in range(d):
    array = move(array)
print(array[0])