Baekjoon 12850. 본대 산책 2 / Python

12850. 본대 산책 2

난이도 : 골드 1
소요 시간 : 15분
날짜 : 2024.12.29
언어 : 파이썬
알고리즘 유형 : 행렬, 그래프, 분할 정복

설명 보기전에 문제 풀어보러 가기

1. 문제 설명

1. 그래프가 주어진다. 만들어야 한다. 귀찮다....
2. d분동안 산책한다.
3. 정보과학관을 돌아오는 경로의 경우의 수를 구한다.

2. 해결 방식

1. 행렬에 대한 이해를 필요로 하는 문제이다.
2. i분 산책한 경로 배열 * j분 산책한 경로 배열 을 하면 i+j분 산책을 한 경로를 구할 수 있다.
   • 이를 활용하면 시간복잡도를 log2(d)로 해결가능.

3. 정답 코드

# 숭실대 지도 그리기
arr = [[0] * 8 for _ in range(8)]
arr[0][1], arr[1][0] = 1, 1
arr[0][2], arr[2][0] = 1, 1
arr[1][2], arr[2][1] = 1, 1
arr[1][3], arr[3][1] = 1, 1
arr[2][3], arr[3][2] = 1, 1
arr[2][4], arr[4][2] = 1, 1
arr[3][4], arr[4][3] = 1, 1
arr[3][5], arr[5][3] = 1, 1
arr[4][5], arr[5][4] = 1, 1
arr[4][7], arr[7][4] = 1, 1
arr[5][6], arr[6][5] = 1, 1
arr[6][7], arr[7][6] = 1, 1
div = 1000000007

def sol(d, grp = arr):
    if d == 1:
        return grp
    grp_n = sol(d // 2, grp)
    if not d % 2:
        return multiple(grp_n, grp_n)
    else:
        return multiple(multiple(grp_n, grp_n), grp)

def multiple(x, y):
    res = [[0]*8 for _ in range(8)]
    for i in range(8):
        for j in range(8):
            for m in range(8):
                res[i][j] += x[i][m] * y[m][j]
            res[i][j] %= div
    return res

ans = sol(int(input()))
print(ans[0][0])