[파이썬/python] 백준 - 29704 벼락치기

문제

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

---

문제 설명

1. N개의 문제와 제출기한 T일이 주어지고, 각 문제 별 소요되는 일 수와 벌금이 주어진다.
2. 제출기한 T일이 지났을 때 내는 벌금의 총금액이 최소가 되도록 하려고 한다.

 

---

풀이

문제를 보고 배낭 알고리즘이 생각났다.

배낭문제는 N개의 아이템이 존재할 때 총 W의 무게를 넘기지 않으면서 가치의 합이 최대가 되도록 하는 문제이다.

 

이 문제의 차이점은 가치의 합이 최대가 아니라 최소가 되어야 한다는 것이다. 하지만 알고리즘의 큰 틀은 벗어나지 않기 때문에 빠르게 2차원 표를 만들어서 검증한 후 점화식을 세웠다.

 

문제에 나와있는 1번 예제를 통해 답을 검증했다.

3 3
2 5000
1 1000
1 2000

 

0번 문제

금액 / 일	0	1	2	3
-	8000	8000	8000	8000
5000
1000
2000

어떤 문제도 해결하지 못했기 때문에 최대 벌금인 모든 벌금의 합을 채워 넣는다.

 

1번 문제

금액 / 일	0	1	2	3
-	8000	8000	8000	8000
5000
1000
2000

1번 문제는 총 2일이  소요된다.

이때 구할 수 있는 경우의 수는 총 2가지이다.

1. 현재 날로부터 이전 문제까지의 최소 벌금

2. 소요되는 일 수 전날까지 해결했던 벌금 - 현재 해소할 벌금

 

1번 문제는 총 2일이 소요되며, 제출 기한은 총 3일이다.

그럼 위에서 구한 경우의 수에 따라 문제를 해결해 보자.

금액 / 일	0	1	2	3
-	8000	8000	8000	8000
5000	8000	8000	8000	8000
1000
2000

첫 번째 문제를 풀기 전에는 모두 8000의 벌금을 가지고 있기 때문에 이처럼 갱신한다.

 

이제 2번의 경우이다.

 

1번 문제는 해결하는데 총 2일이 걸리게 되고 제출 기한이 3일이기 때문에

2일 차가 되었을 때 0일 차까지 해결한 벌금에서 현재 벌금을 뺄 수 있는 경우가 존재한다.

또한 3일 차가 되었을 때 1일 차까지 해결한 벌금에서 현재 벌금을 뺄 수 있는 경우가 존재한다.

 

그럼 이를 식으로 세우게 되면

i = 물건 idx, j = 현재 일, dp[i][j] = 남은 벌금 일 때

dp[i-1][j] (이전 물건에서 현재까지 구한 최소 벌금)와

dp[i-1][j-day] - cost(현재 날로부터 소요되는 일을 뺀 날까지의 벌금에서 현재 벌금을 뺀 나머지 값)을 비교하면 최소 값을 구할 수 있다.

 

그럼 이제 2번 경우의 수를 구해보자.

1번 문제의 2일 차 = 0번 문제의 0일 차 벌금 - 1번 문제의 벌금 = 3000

1번 문제의 3일 차 = 0번 문제의 1일 차 벌금 - 1번 문제의 벌금 = 3000

금액 / 일	0	1	2	3
-	8000	8000	8000	8000
5000	8000	8000	3000	3000
1000
2000

따라서 표를 갱신하면 다음과 같이 된다.

 

이와 같이 두 번째, 세 번째 물건도 갱신해 보자.

 

2번 문제

금액 / 일	0	1	2	3
-	8000	8000	8000	8000
5000	8000	8000	3000	3000
1000	8000	7000	3000	2000
2000

2번 문제의 0일 차

1번 문제의 0일 차 벌금 = 8000

 

2번 문제의 1일 차

1번 문제의 0일 차 벌금 - 2번 문제의 벌금 = 7000

1번 문제의 1일 차까지의 벌금 = 8000

 

2번 문제의 2일 차

1번 문제의 1일 차 벌금 - 2번 문제의 벌금 = 7000 

1번 문제의 2일 차까지의 벌금 = 3000

 

2번 문제의 3일 차

1번 문제의 2일 차 벌금 - 2번 문제의 벌금 = 2000

1번 문제의 3일 차까지의 벌금 = 3000

 

3번 문제

금액 / 일	0	1	2	3
-	8000	8000	8000	8000
5000	8000	8000	3000	3000
1000	8000	7000	3000	2000
2000	8000	6000	3000	1000

3번 문제의 0일 차

2번 문제의 0일 차 벌금 = 8000

 

3번 문제의 1일 차

2번 문제의 0일 차 벌금 - 3번 문제의 벌금 = 6000

2번 문제의 1일 차까지의 벌금 = 7000

 

3번 문제의 2일 차

2번 문제의 1일 차 벌금 - 3번 문제의 벌금 = 5000 

2번 문제의 2일 차까지의 벌금 = 3000

 

3번 문제의 3일 차

2번 문제의 2일 차 벌금 - 3번 문제의 벌금 = 1000

2번 문제의 3일 차까지의 벌금 = 2000

 

최종적으로 마지막 문제의 마지막 벌금을 구하게 되면 최소 벌금을 구할 수 있다.

따라서 dp 점화식은 아래와 같다.

dp[i][j] = min(dp[i-1][j], dp[i-1][j-weight] - cost)

 

 

배낭 문제는 익숙해지면 문제만 봐도 무게, 가치 => 최대 합이라는 익숙한 흐름이 바로 보이게 되는 것 같다.

문제만 읽어도 알고리즘을 파악할 수 있다는 것은 정말 큰 장점이기 때문에 배낭 문제의 여러 유형을 풀어보면서 최대한 이 알고리즘에 익숙해지는 것을 추천한다.

 

---

코드

import sys
input = sys.stdin.readline


N,T = map(int,input().split())
items = [[0,0]] + [list(map(int,input().split())) for _ in range(N)]

MAX = 0
for i in items:
    MAX  += i[1]

dp = [[0 for _ in range(T+1)] for _ in range(N+1)]
for i in range(T+1):
    dp[0][i] = MAX

for i in range(1,N+1):
    weight,cost = items[i]
    for j in range(T+1):
        if j - weight < 0:
            dp[i][j] = dp[i-1][j]
        else:
            dp[i][j] = min(dp[i-1][j], dp[i-1][j-weight] - cost)

print(dp[-1][-1])

 

---

시간복잡도

• N개의 아이템을 T일동안 갱신하기 때문에 $O(N*T)$의 시간복잡도를 가진다.
• N은 최대 1000, T는 최대 1000 이므로 약 $O(10^6)$ 시간복잡도를 가지게 된다.