https://www.acmicpc.net/problem/14501
14501번: 퇴사
첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다.
www.acmicpc.net
문제 해결을 위한 과정
이 문제는 전형적인 다이나믹 프로그래밍 문제 중에 하나입니다. 예시를 기준으로 1일부터 7일까지의 T, P 값을 이용하여 문제를 해결하면 됩니다. 예시를 기준으로 설명을 하겠습니다.
1일까지 최대한 많은 금액을 받을수 있는 일정은 1일째만 일하는 10원입니다.
2일까지 최대한 많은 금액을 받을 수 있는 일정은 2일째만 일하는 20원 입니다.
3일까지 최대한 많은 금액을 받을 수 있는 일정은 2일째만 일하는 20원입니다.
4일까지 최대한 많은 금액을 받을 수 있는 일정은 1일째, 4일째 일하는 30원입니다.
5일까지 최대한 많은 금액을 받을 수 있는 일정은 1일째, 4일째, 5일째 일하는 45원입니다.
6일까지 최대한 많은 금액을 받을 수 있는 일정은 1일째, 4일째, 5일째 일하는 45원입니다.
7일까지 최대한 많은 금액을 받을 수 있는 일정은 1일째, 4일째, 5일째 일하는 45원입니다.
따라서 우리는 먼저 0으로 전부 초기화 한 dp라는 리스트를 생성한 후 해당하는 날짜와 해당 날짜에서 T만큼 지난날을 P로 초기화를 해주면 됩니다. 예시는 다음과 같습니다.
먼저 전체가 0으로 된 리스트를 생성합니다.
| 0 | 0 | 0 | 0 | 0 | 0 | 0 |
1일째 일을 하면 4일째부터 일을 할 수 있으므로 1일에 P를 더해주고 4일째부터는 1일째의 dp값과 해당 날짜의 dp값의 max값을 넣어준다.
| 10 | 0 | 0 | 10 | 10 | 10 | 10 |
2일째 일을 하면 7일째부터 일을 할 수 있으므로 2일에 P를 더해주고 7일째부터는 2일째의 dp값과 해당 날짜의 dp값의 max값을 넣어준다.
| 10 | 20 | 0 | 10 | 10 | 10 | 20 |
3일째 일을 하면 4일째부터 일을 할 수 있으므로 3일에 P를 더해주고 4일째부터는 3일째의 dp값과 해당 날짜의 dp값의 max값을 넣어준다.
| 10 | 20 | 10 | 10 | 10 | 10 | 20 |
4일째 일을 하면 5일째부터 일을 할 수 있으므로 4일에 P를 더해주고5일째부터는 4일째의 dp값과 해당 날짜의 dp값의 max값을 넣어준다.
| 10 | 20 | 10 | 30 | 30 | 30 | 30 |
5일째 일을 하면 7일째부터 일을 할 수 있으므로 5일에 P를 더해주고7일째부터는 5일째의 dp값과 해당 날짜의 dp값의 max값을 넣어준다.
| 10 | 20 | 10 | 30 | 45 | 30 | 45 |
그 뒤로 6일째와 7일째는 일이 끝나는 날이 N을 벗어나므로 고려하지 않는다.
백준이가 얻을 수 있는 최대 수익은 dp리스트의 max값인 45이다.
소스코드
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
|
n = int(input())
data = [0]
ans = [0]*(2+n)
for i in range(1, n+1):
t, p = map(int, input().split())
data.append((i, t, p))
for i in range(1, n+1):
day, t, p = data[i]
if day + t <= n+1:
ans[i] += p
for j in range(day+t, n+1):
ans[j] = max(ans[day], ans[j])
print(max(ans))
|
cs |
'알고리즘 > 백준' 카테고리의 다른 글
| 백준 알고리즘 2437: 저울 (Python) (0) | 2021.01.03 |
|---|---|
| 백준 알고리즘 18353: 병사 배치하기(Python) (0) | 2020.12.21 |
| 백준 알고리즘 1932: 정수 삼각(Python) (0) | 2020.12.18 |
| 백준 알고리즘 2110: 공유기 설치 (Python) (0) | 2020.12.18 |
| 백준 알고리즘 18310: 안테나(Python) (2) | 2020.12.10 |