[백준 11444번] 피보나치 수 6 (Python3)
문제의 압도적인 n의 제한범위 (n은 1,000,000,000,000,000,000보다 작거나 같은 자연수)를 보자마자 분할정복 거듭제곱으로 푸는거구나 를 깨닫긴 했는데, 어떻게 풀어야 할지 막막했다. 그렇게 끄적끄적 고민하다가 놀라운 사실을 발견했는데, 바로 피보나치 수가 피보나치 수를 피보나치 수의 곱으로 나타낼 수 있다는 것이었다. 발견하게된 이유는 3은 1+2인데, 5는 2+3이다. 그런데 5는 2+(1+2)이므로 1이 1번 2가 2번 쓰인다. 8은 5+3이므로 2+3+3이고, 이는 2+(1+2)+(1+2) 이다. 2가 3번, 1이 2번 쓰인다. 규칙이 보이지 않는가? 작은 숫자들의 개수도 똑같이 피보나치 수열인 것이다. 이 규칙을 이용해 조금 만지다 보면 이런 식을 발견할 수 있다. n이 홀수일..
[백준 11779번] 최소비용 구하기 2 (Python3)
import sys input = sys.stdin.readline from collections import deque import heapq INF = sys.maxsize N = int(input()) M = int(input()) graph = [[] for i in range(N+1)] money = [INF]*(N+1) route = [[] for i in range(N+1)] for i in range(M): x1,x2,w = map(int,input().split()) graph[x1].append((x2,w)) start,goal = map(int,input().split()) hq = [] heapq.heappush(hq,(0,start,0)) while hq: w,x,last = he..