문제 링크: https://www.acmicpc.net/problem/14501
요약: 상담을 적절히 했을 때, 백준이가 얻을 수 있는 최대 수익을 구하는 프로그램을 작성하시오.
- 입력 받기
customers = []
for _ in range(N):
customers.append(list(map(int, input().split())))customers라는 배열을 선언하고, [고객상담에 걸리는 일수, 얻을 수 있는 보상] 정보를 저장합니다.
1. dfs를 활용한 완전 탐색 방법
고객 상담을 할지 않할지 분기를 이용해 재귀적으로 풀어보았습니다.
if idx >= len(customers):
global_max = max(sum, global_max)
return종료조건은 다음과 같습니다.
매일같이 받을 수 있는 고객이 있기 때문에, 고객의 길이는 퇴사하려는 날짜와 동일합니다.
따라서, 현재 날짜(idx)가 퇴사일(len(customers))을 넘어간다면 현재 날짜의 고객은 선택할 수 없습니다.
즉, 현재 case의 pay(sum)와 지금까지 max값(global_max)을 비교해 갱신해 줍니다.
# 고객 상담
if idx + customers[idx][0] <= N:
dfs_choose_schadule(N, customers, idx + customers[idx][0], sum + customers[idx][1])
# 고객 상담 x
dfs_choose_schadule(N, customers, idx + 1, sum)만약 상담이 가능하다면, 그 고객을 상담할 것인지 아닌지로 분기를 나누어줍니다.
고객을 상담한다면, 현재일에서 해당 고객을 상담하는데 걸리는 일 수가 퇴사일을 넘으면 안됩니다. 조건문을 통해, 퇴사일을 넘지 않을 때만 상담하는 분기로 넘어 갑니다.
그렇지 못한경우에는 고객을 상담하지 않고 넘어 갑니다.
재귀문이 끝난 경우 모든 경우의 수를 탐색해 가장 높게 받을 수 있는 pay가 global_max에 저장됩니다.
2. Dp를 활용한 탐색 방법
Dynamic programming을 활용한 경우 다음과 같이 풀이가 가능합니다.
# 해당 일자(index)에 최대로 받을 수 있는 금액
dp = [0] * (N + 1)우선 Dp 배열을 위와 같이 정의합니다. (처음엔 모두 0)
그리고 max_money라는 변수를 활용해 다음과 같이 풀이가 가능합니다.
- Dp[1]은 아직일을 하지 않았기 때문에 수입이 없어 0입니다. 그리고 만약 일을 수행한다면 3일 후인 Dp[1+3]에 10이라는 보상을 얻게 됩니다.
- Dp[2]도 마찬가지로 얻는 수입은 없습니다. 그리고 해당 일을 수행했을 때 5일 후인 Dp[2+5]에 20이라는 보수를 얻습니다.
- Dp[3]도 마찬가지 수입은 0입니다. 그리고 일을 하게되면 1일 후에 10이라는 보상을 얻습니다.
- Dp[4]는 Dp[1]에서 일을 수행했기 때문에 최대로 얻을 수 있는 보상은 10입니다. 따라서 현재까지 가장 많이 얻을 수 있는 수입이 10임으로, max_money는 10이 됩니다. 그리고 일을 수행했다면, 1일 후인 Dp[4+1]에 30(현재최대보상 10 + 일한 보수 20)이라는 보상을 업을 수 있습니다.
- Dp[5]는 현재 최대 30의 보수를 얻을 수 있습니다. 동일하게 max_money는 업데이트됩니다. 그리고 일을 수행하면 Dp[5+2]에 30 + 15로 45라는 보수를 얻을 수 있습니다.
- Dp[6]에서는 해당일을 수행하는 것은 불가능합니다. Dp[6]은 0이지만, 이전 일수 까지 최대값이 30이었기 때문에 6일차도 누적 30이라는 최대의 보수를 획득할 수 있습니다. 따라서 Dp[6] = 30이 됩니다.
- Dp[7]에서는 45라는 보수를 얻을 수 있습니다. 따라서 max_money가 45로 업데이트됩니다. 그리고 해당일차의 일은 수행할 수 없습니다.
결과적으로 45가 최대로 얻을 수 있는 보수가 됩니다.
이것을 구현하면 다음과 같습니다.
max_money = 0
for idx in range(N + 1):
dp[idx] = max(max_money, dp[idx])
# idx번째 업무 + 걸리는 일수
next = idx + customers[idx][0]
if (next < N + 1): # 퇴사일을 넘어가지 않으면
dp[next] = max(dp[next], customers[idx][1] + dp[idx])
max_money = max(max_money, dp[idx])전체 코드는 다음과 같습니다.
chatGPT를 이용해 최적화도 한번 해보았습니다.
global_max = 0
def dfs_choose_schadule(N, customers, idx, sum):
global global_max
if idx >= len(customers):
global_max = max(sum, global_max)
return
# 고객 상담
if idx + customers[idx][0] <= N:
dfs_choose_schadule(N, customers, idx + customers[idx][0], sum + customers[idx][1])
# 고객 상담 x
dfs_choose_schadule(N, customers, idx + 1, sum)
def dp_choose_schedule(dp, N, customers):
max_money = 0
for idx in range(N + 1):
#
dp[idx] = max(max_money, dp[idx])
# idx번째 업무 + 걸리는 일수
next = idx + customers[idx][0]
if (next < N + 1): # 퇴사일을 넘어가지 않으면
dp[next] = max(dp[next], customers[idx][1] + dp[idx])
max_money = max(max_money, dp[idx])
return max_money
# chatGPT 최적화
def caht_dp_choose_schedule(customers):
dp = [0] * (len(customers))
max_money = 0
for idx, (duration, reward) in enumerate(customers):
max_money = max(max_money, dp[idx])
next = idx + duration
if next < len(customers):
dp[next] = max(dp[next], reward + max_money)
return max_money
def solution():
global global_max
N = int(input())
customers = []
for _ in range(N):
customers.append(list(map(int, input().split())))
dfs_choose_schadule(N, customers, 0, 0)
customers.append([0, 0])
# 해당 일자(index)에 최대로 받을 수 있는 금액
dp = [0] * (N + 20)
max_money = dp_choose_schedule(dp, N, customers)
chat_max_money = caht_dp_choose_schedule(customers)
return global_max, max_money, chat_max_money
if __name__ == "__main__":
answer = solution()
print(answer)