[BOJ] 12849. 본대 산책(경로 DP)py,cpp

#. Problem

https://www.acmicpc.net/problem/12849

* The copyright in this matter is in BOJ

#. Resolution Process

  1. Read and understand problem

  2. Redefine the problem + abstract

  3. Create solution plan (select Algorithm, Data structure)

  4. Prove the plan (check performance time and usage memory)

  5. Carry out the plan

  6. Look back on the plan and find a way to improve it

#. Solve

경로 DP문제는

DP문제에서도 전형적이고 코테 문제와 유사한 형태를 가지고 있는 문제라고 한다.

그리고 이 문제처럼

index를 주지 않는 문제는 자체적으로 index를 정의해주고 그 index에 따라 식을 만들어야 한다.

여기서는 우선

초기 DP[]에 0분에 어떤 지점에 도달할 수 있는 상태를 정의하고

다음 상태에 따른 변화를 점화식으로 세워주면 된다.

마지막에

1000000007, 1000000009 와 같은 수로 나눈 나머지를 답으로 제출하라고 하는 문제가 종종 있는데, 

이 수는 소수이고 어떤 답에 대한 해시값을 출력하라는 의미이다.

C에서는 수가 커지면 int overflow를 방지하기 위한 방법으로 나머지 출력하라고 하는 경우고 있는데,

파이썬은 수의 범위가 어느정도 크기때문에 마지막에 나눠주면 된다. (C, Java의 경우 각 연산에 대하여 나머지를 연산 필요)

하지만 속도 측면에서 나눗셈연산이 상당히 무거워서 나눗셈 연산을 많이 하는게 좋은 방법은 아니지만

속도면에서 미리 나눗셈 연산을 해주면 나중에 큰 수의 나눗셈을 수행하는 것 보다 효율적인 결과를 볼 수 있다. 

동작을 살펴보면,

먼저 문제에서 index를 주지 않았기 때문에 index를 정의해야 한다.

# 0 : 정보과학관

# 1 : 전산관

# 2 : 신앙관

# 3 : 미래관

# 4 : 진리관

# 5 : 환경직기념관

# 6 : 학생회관

# 7 : 형남공학관

정보과학관에서 출발하여 정보과학관으로 돌아와야 하므로 

초기 0분에 DP의 상태는 아래 표와 같다

정보과학관	전산관	신앙관	미래관	진리관	한경직기념관	학생회관	형남공학관
1	0	0	0	0	0	0	0

산책 1분 후 상태,

정보과학관과 연결된 전산관, 미래관으로 이동할 수 있다.

정보과학관	전산관	신앙관	미래관	진리관	한경직기념관	학생회관	형남공학관
0	1	0	1	0	0	0	0

산책 2분 후 상태

정보과학관은 전산관에서 정보과학관으로 돌아오는 경우, 미래관에서 정보과학관으로 돌아오는 경우 2가지 경우가 있고,

신앙관은 전산관에서 가는 경우, 미래관에서 가는 경우 2가지 경우가 있고,

한경직기념관은 미래관에서 가는 경우 1가지 경우가 있다.

정보과학관	전산관	신앙관	미래관	진리관	한경직기념관	학생회관	형남공학관
2	1	2	1	0	1	0	0

산책 3분 후 상태

정보과학관	전산관	신앙관	미래관	진리관	한경직기념관	학생회관	형남공학관
2	5	3	6	3	3	0	1

...

결국 정보과학관 = n분 후 전산관으로 도착할 수 있는 상태 + n분 후 미래관으로 도착할 수 있는 상태가 되고,

전산관 = n분 후 정보과학관으로 도착할 수 있는 상태 + n분 후 신앙관으로 도착할 수 있는 상태 + n분 후 미래관으로 도착할 수 있는 상태가 된다.

나머지 지점들도 마찬가지로 1분 후 상태에 따른 점화식을 세울 수 있다.

#. Code

DP = [1, 0, 0, 0, 0, 0, 0, 0]
# 0 : 정보과학관
# 1 : 전산관
# 2 : 신앙관
# 3 : 미래관
# 4 : 진리관
# 5 : 환경직기념관
# 6 : 학생회관
# 7 : 형남공학관
def move(state):
    tmp = [0 for _ in range(8)]
    tmp[0] = state[1] + state[3]
    tmp[1] = state[0] + state[2] + state[3]
    tmp[2] = state[1] + state[3] + state[4] + state[5]
    tmp[3] = state[0] + state[1] + state[2] + state[5]
    tmp[4] = state[2] + state[5] + state[6]
    tmp[5] = state[3] + state[2] + state[4] + state[7]
    tmp[6] = state[4] + state[7]
    tmp[7] = state[5] + state[6]
 
    for i in range(8):
        tmp[i] %= 1000000007
    return tmp
 
for i in range(int(input())):
    DP = move(DP)
 
print(DP[0])

line 1) 0분에 어떤 지점에 도착할 수 있는 상태

line 10) 1분 후 상태에 따른 점화식

line 21~22) 미리 나눗셈 연산을 수행