[다익스트라+DP] 15486번,10282번

1. 퇴사2

코드

import sys
input = sys.stdin.readline
n = int(input())

t_arr=[]
p_arr=[]

for _ in range(n):
    t,p = map(int,input().split())
    t_arr.append(t)
    p_arr.append(p)

max_val = 0
dp=[0]*(n+1)
#top-down
for i in range(n-1,-1,-1):
    time = i+t_arr[i]
    #일이 기간 내에 끝난다면
    if time<=n:
        dp[i]+= max(max_val, p_arr[i]+dp[time])
        max_val=dp[i]
    else:
        dp[i] = max_val

print(max_val)

퇴사1 문제와 동일했다. 다른 점은 n의 범위가 1<=n<=50이여서 bottom-up방식을 사용하기가 더 어려워진다는 점?
물론 난 거꾸로 계산해줘서 상관은 없었다.

2. 해킹

코드

import heapq
import sys
input = sys.stdin.readline

INF = int(1e9)
#테케 개수 입력
t = int(input())

def dijkstra(start):
    q=[]
    visited[start]=True
    dist[start]=0
    heapq.heappush(q,(0,start))#dist,node
    
    while q:
        distance, node = heapq.heappop(q) #노드 선택
        if dist[node] < distance: #이미 방문했었던 노드라면 무시
            continue
        
        for i in graph[node]:
            cost = distance+i[1] #노드를 거쳐갔을 때의 비용
            if cost<dist[i[0]]:
                dist[i[0]] = cost
                heapq.heappush(q,(cost,i[0]))

for _ in range(t):
    n,d,c = map(int,input().split())
    graph = [[] for i in range(n+1)]
    visited=[False]*(n+1)
    dist=[INF]*(n+1)
    
    #간선 개수만큼 입력
    for i in range(d):
        a,b,s = map(int,input().split())
        graph[b].append([a,s])
    
    #다익스트라 실행
    dijkstra(c)
    #개수
    count = n-dist.count(INF)+1
    
    #걸린 비용 탐색
    time=0
    for i in range(1,n+1):
        if dist[i]==INF:
            continue
        else:
            if time<dist[i]:
                time=dist[i]
    print(count,time)

다익스트라를 아예 까먹은거 같아서 기본 문제를 풀어보았다.

첫번째는 간단한 다익스트라 알고리즘을 사용해서 구현했는데 시간초과가 났어서, heapq를 사용하는 다익스트라 알고리즘을 이용해서 풀었다.

제출할 때 c++로 체크해두고 테스트를 돌렸다던지 등의.. 여러 번의 자잘한 헛짓거리 끝에 성공했다...