행렬 썸네일형 리스트형 백준 12850 본대 산책 2 https://www.acmicpc.net/problem/12850 12850번: 본대 산책2 가능한 경로의 수를 1,000,000,007로 나눈 나머지를 출력한다. www.acmicpc.net N = 10억이므로 시간복잡도가 기존의 O(N)인 알고리즘 또한 먹히지 않는다. (물론 10억 개수의 변수를 메모리 공간에 저장하려고 하면 메모리 초과가 날 것이다.) Vertex 사이의 거리가 모두 같다는 점을 이용해서 그래프의 인접행렬의 거듭제곱을 하면 O(8*8*logN)시간에 경우의 수를 구할 수 있다. package 백준; import java.util.Scanner; public class 본대산책2 { static long map[][]; public static void main(String[] a.. 더보기 이전 1 다음