DP(본대 산책/S1) - 12849

1. 문제

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

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

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

 

2. 입력

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

 

10

 

3. 출력

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

 

9857

 

4. 코드

import sys

d = int(sys.stdin.readline())
road = [1,0,0,0,0,0,0,0]
# 0 : 정보과학관
# 1 : 전산관
# 2 : 신앙관
# 3 : 미래관
# 4 : 진리관
# 5 : 환경직기념관
# 6 : 학생회관
# 7 : 형남공학관

def dp(road):
  map = [0  for _ in range(8)]
  map[0] = (road[1] + road[3]) % 1000000007
  map[1] = (road[0] + road[2] + road[3]) % 1000000007
  map[2] = (road[1] + road[3] + road[4] + road[5]) % 1000000007
  map[3] = (road[0] + road[1] + road[2] + road[5]) % 1000000007
  map[4] = (road[2] + road[5] + road[6]) % 1000000007
  map[5] = (road[2] + road[3] + road[4] + road[7]) % 1000000007
  map[6] = (road[4] + road[7]) % 1000000007
  map[7] = (road[5] + road[6]) % 1000000007

  return map

for i in range(d):
  road = dp(road)
print(road[0])

 

5. 풀이설명

① 입력값 d를 입력받는다.

 

② 0 ~ 7까지를 각 건물 번호로 설정하고 [1,0,0,0,0,0,0] 초기값 배열 road를 생성한다.

- 0분동안 정보과학관으로 갈 수 있는 방법

 

③ 반목문을 d 만큼 실행하는데 road를 인자인 dp 함수를 실행한다.

 

④ dp 함수 실행시 0으로 이루어진 map 함수를 생성한다.

 

⑤ 건물번호와 같은 index를 가진 map에 그 건물과 이어진 건물번호의 index의 road 값들을 더해서 대입한다.

 

⑥ dp 함수 결과 map 배열을 반환한다.

 

⑦ 반복문 결과 정보관까지 가는 방법인 road[0]을 결과값으로 출력한다.

 

6. 느낀점

방법을 못찾아서 구글링을 했다. 트리구조나 좌표를 찾아가는 문제는 이전 노드까지 가는 방법의 갯수를 찾는 방식으로 접근 해야겠다.