백준 12849번. 본대 산책 (Python / 파이썬)

문제

숭실 대학교 정보 과학관은  캠퍼스의 길 건너편으로 유배를 당했다. 그래서 컴퓨터 학부 학생들은 캠퍼스를 ‘본대’ 라고 부르고 정보 과학관을 ‘정보대’ 라고 부른다. 준영이 또한 컴퓨터 학부 소속 학생이라서 정보 과학관에 박혀있으며 항상 본대를 가고 싶어 한다. 어느 날 준영이는 본대를 산책하기로 결심하였다. 숭실 대학교 캠퍼스 지도는 아래와 같다.

(편의 상 문제에서는 위 건물만 등장한다고 가정하자)

한 건물에서 바로 인접한 다른 건물로 이동 하는 데 1분이 걸린다. 준영이는 산책 도중에 한번도 길이나 건물에 멈춰서 머무르지 않는다. 준영이는 할 일이 많아서 딱 D분만 산책을 할 것이다. (산책을 시작 한 지 D분 일 때, 정보 과학관에 도착해야 한다.) 이때 가능한 경로의 경우의 수를 구해주자.

입력

D 가 주어진다 (1 ≤ D ≤ 100,000) 

출력

가능한 경로의 수를 1,000,000,007로 나눈 나머지를 출력 한다.

---

문제 풀이 

한 건물에서 다른 건물로 이동 하는 데 1분이 걸린다. 

따라서 1분, 2분, 3분, ... 1분이 지날때마다 각 건물에 준영이가 도달할 수 있는 경우의 수를 구할 수 있다. 

각 건물에 준영이가 도달할 수 있는 경우의 수는 건물과 연결되어있는 이전 건물들의 경우의 수를 모두 더해주는 것이다. 

위의 그림처럼 각 건물에 0부터 7까지 번호를 붙였다고 할 때 

위의 표와 같이 1분이 지날 때마다 준영이가 각 건물에 도달하는 경우의 수를 구할 수 있다. 

각 건물에 준영이가 도달할 수 있는 경우의 수는 건물과 연결되어있는 이전 건물들의 경우의 수를 모두 더해주는 것이므로

건물[0] = 건물[1] + 건물[2]

건물[1] = 건물[0] + 건물[2] + 건물[3] 

이와 같이 구할 수 있다. 

 

즉, 총 D분 동안 반복하여 이렇게 계산해주면 배열의 0번째에 D분이 지났을 때 정보과학관에 도착하는 산책 경로의 경우의 수가 저장되어있을 것이다. 

---

My Code 

D = int(input())
dp = [0] * 8
dp[0] = 1 

for i in range(D):
    tmp = [0] * 8
    tmp[0] = dp[1] + dp[2]
    tmp[1] = dp[0] + dp[2] + dp[3]
    tmp[2] = dp[0] + dp[1] + dp[3] + dp[4]
    tmp[3] = dp[1] + dp[2] + dp[4] + dp[5]
    tmp[4] = dp[2] + dp[3] + dp[5] + dp[6]
    tmp[5] = dp[3] + dp[4] + dp[7]
    tmp[6] = dp[4] + dp[7]
    tmp[7] = dp[5] + dp[6]

    for i in range(8):
        dp[i] = tmp[i] % 1000000007

print(dp[0])