삶은 여행

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

x = int(input()) 
dp = [0] * (x+1) 
for i in range(1, x+1): 
    dp[i] = i 
    for j in range(1, i): 
        if (j * j) > i: 
            break 
        dp[i] = min(dp[i], dp[i - j**2] + 1) 

print(dp[x])

python으로 제출하면 시간초과가 난다. pypy3으로 제출했다.

32, 64, 128 등의 반례를 찾았기 때문에

가까운 제곱수 항 개수를 생각하는 것이 아니라

여태까지 나온 모든 제곱수 항을 확인해봐야한다는 것에 착안해야한다.

​

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

import heapq
import sys

n, e = map(int, sys.stdin.readline().split())
s = int(input())
a = [[]for _ in range(n+1)]
for _ in range(e):
    u, v, w = map(int, sys.stdin.readline().split())
    a[u].append((w, v))
INF = 10 * n + 1
d = [INF] * (n+1)
d[s] = 0
queue = []
heapq.heappush(queue, (0,s))
while queue:
    cost, now = heapq.heappop(queue)

    for x, next_node in a[now]:
        xc = x + cost
        if xc < d[next_node]:
            d[next_node] = xc
            heapq.heappush(queue, (xc, next_node))

for i in range(1, n+1):
    if d[i]==INF:
        print('INF')
    else: print(d[i])

다익스트라 알고리즘을 처음 익히기에 좋은 문제였다. 

경로 가중치의 조건이 10 이하의 자연수라는 점에서 INF를 10*n + 1 로 설정해서 수월하게 풀 수 있었다. 

다익스트라 알고리즘을 구현할 때 힙 구조를 많이 사용한다고 하여 힙 구조에 대해 복습했다.

힙 구조 안에 리스트를 넣는 방법으로 삼중 리스트로 해결해도 되지만 개인적으로 편한 튜플로 해결했다.

​

​

참조 : https://sungmin-joo.tistory.com/33

https://hsp1116.tistory.com/42

www.acmicpc.net/problem/2193

n = int(input())
dp = [0,1,1]
for i in range(3,n+1):
    dp.append(dp[i-1]+dp[i-2])
print(dp[-1])

몇 개씩 나오는지 케이스를 나열해봤더니

1,1,2,3,5,8,13,21 ... 의 형태로 나와서 바로 풀 수 있었다.