2157번: 여행
첫째 줄에 N(1 ≤ N ≤ 300), M(2 ≤ M ≤ N), K(1 ≤ K ≤ 100,000)가 주어진다. K는 개설된 항공로의 개수이다. 다음 K개의 줄에는 각 항공로에 대한 정보를 나타내는 세 정수 a, b, c(1 ≤ a, b ≤ N, 1 ≤ c ≤ 1
www.acmicpc.net
코드
import sys
input = sys.stdin.readline
n, m, k = map(int, input().split())
path = [[-1]*(n+1) for _ in range(n+1)] # path[i][j] : i->j로 갈 때 기내식 점수
for _ in range(k):
a, b, c = map(int, input().split())
if a < b: # 동->서로 가는 경우에만 기내식 점수 저장
path[a][b] = max(path[a][b], c)
# dp[i][j] : i번 도시까지 j개의 도시를 지나며 먹는 기내식 점수 총 합의 최대값
dp = [[-1]*(m+1) for _ in range(n+1)]
dp[1][1] = 0
for i in range(2, n+1):
for j in range(2, m+1):
for k in range(1, i): # 나보다 동쪽에 있는 도시들 모두 탐색
if dp[k][j-1] >= 0 and path[k][i] > 0:
dp[i][j] = max(dp[i][j], dp[k][j-1]+path[k][i])
ans = 0
for i in range(1, m+1):
ans = max(ans, dp[n][i])
print(ans)
처음에 BFS로 풀이했더니 메모리 초과가 발생했다. 메모리 제한은 128mb인데 BFS를 진행하며 큐에 들어가는 원소들이 너무 많아서 그랬던것 같다. 그래서 DP로 다시 풀이했다.
dp[i][j] : i번 도시까지 j개의 도시를 지나며 먹는 기내식 점수의 총 합의 최대값을 저장한다. 그러므로 dp[i][j]의 값을 구할 때는 나보다 동쪽에 있는 도시, 즉 번호가 작은 모든 도시(for k in range(1, i))들에 j-1개의 도시를 거쳐서 도달할 때의 값인 dp[k][j-1]에 k번 도시에서 i번 도시로 올 때 먹는 기내식 점수인 path[k][i]를 더한 값(dp[k][j-1]+path[k][i])과 기존의 dp[i][j]을 비교하여 더 큰 값을 저장하면 된다.
이렇게 모두 구한 뒤 n에 도달했을 때 m개 이하의 도시를 지나며 얻을 수 있는 기내식의 점수의 총 합의 최대값을 구하면 된다. dp[n][1:m+1]에 저장된 값 중 최대값이 그 답이다.
'문제풀이 > DP' 카테고리의 다른 글
[Python/파이썬] 백준 21923번 곡예 비행 (0) | 2024.04.26 |
---|---|
[Python/파이썬] 백준 15993번 1, 2, 3 더하기 8 (1) | 2024.04.25 |
[Python/파이썬] 백준 1757번 달려달려 (0) | 2024.04.09 |
[Python/파이썬] 백준 2670번 연속부분최대곱 (0) | 2024.04.04 |
[Python/파이썬] 백준 1823번 수확 (0) | 2024.02.16 |