퇴사 (실버3)

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

문제

상담원으로 일하고 있는 백준이는 퇴사를 하려고 한다.

오늘부터 N+1일째 되는 날 퇴사를 하기 위해서, 남은 N일 동안 최대한 많은 상담을 하려고 한다.

백준이는 비서에게 최대한 많은 상담을 잡으라고 부탁을 했고, 비서는 하루에 하나씩 서로 다른 사람의 상담을 잡아놓았다.

각각의 상담은 상담을 완료하는데 걸리는 기간 Ti와 상담을 했을 때 받을 수 있는 금액 Pi로 이루어져 있다.

N = 7인 경우에 다음과 같은 상담 일정표를 보자.

 1일2일3일4일5일6일7일TiPi

3	5	1	1	2	4	2
10	20	10	20	15	40	200

1일에 잡혀있는 상담은 총 3일이 걸리며, 상담했을 때 받을 수 있는 금액은 10이다. 5일에 잡혀있는 상담은 총 2일이 걸리며, 받을 수 있는 금액은 15이다.

상담을 하는데 필요한 기간은 1일보다 클 수 있기 때문에, 모든 상담을 할 수는 없다. 예를 들어서 1일에 상담을 하게 되면, 2일, 3일에 있는 상담은 할 수 없게 된다. 2일에 있는 상담을 하게 되면, 3, 4, 5, 6일에 잡혀있는 상담은 할 수 없다.

또한, N+1일째에는 회사에 없기 때문에, 6, 7일에 있는 상담을 할 수 없다.

퇴사 전에 할 수 있는 상담의 최대 이익은 1일, 4일, 5일에 있는 상담을 하는 것이며, 이때의 이익은 10+20+15=45이다.

상담을 적절히 했을 때, 백준이가 얻을 수 있는 최대 수익을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N (1 ≤ N ≤ 15)이 주어진다.

둘째 줄부터 N개의 줄에 Ti와 Pi가 공백으로 구분되어서 주어지며, 1일부터 N일까지 순서대로 주어진다. (1 ≤ Ti ≤ 5, 1 ≤ Pi ≤ 1,000)

출력

첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다.

 

 

# 풀이

 

주어진 일정 내에서 최대한 많은 수익을 얻기 위한 방법을 도출 해야한다.

 

이 때 바로 생각난 알고리즘은 "그리드" 알고리즘이다.

 

항상 현재 상황에서 최선의 선택을 하여 최종 결과값에서도 최대한의 이익을 벌 수 있다고 생각하였다.

 

가장 짧은 시간에 많은 이익을 벌 수 있는 상담을 받게 하면 될 수 있다고 생각하였다.

 

첫번째의 일정은 3일동안 10의 이익을 낼 수 있으므로 하루에 3.333... 이익을 낸다.

두 번째의 일정은 5일동안 20의 이익 이니 하루에 20/5 = 4 의 이익을 낸다.

 

여기서 고려해야할 건 기회비용측면을 고려하여야 할것이다. 

 

또한 기간 내에서만 상담이 가능한 경우도 고려하여야 한다.

 

입력값의 형태가 쌍으로 주어져 있으므로 튜플형과 리스트를 활용하여 저장하였다.

 

# 입력

N = int(input())

date = []

for _ in range(N):

  T , P = map(int,input().split())

  date.append((T,P))

print(date)

그리고 이미 상담 예약이 되어있는 경우와 기간을 넘어가는 경우를 제외하기 위해 reserved 리스트로 표시하였다.

요소 False : 예약 안됨 True : 예약됨 

reserved 리스트

그리고 상담 기간이 하루이고 예약이 차있지 않은 상태면 다른 상담과 비교할 것 없이 그 일자의 상담을 진행하면 된다.

 

# 접근 실패

 

하지만 쉽게 구해지지 않았다. 처음 그리디 로 접근했던것이 잘못되었다. 

 

일차마다 가장 큰 값을 저장하며 값을 구하는 계단 문제와 양상이 비슷했다.

 

# Dynamic Programming 으로 다시 접근

 

DP 방식으로 접근하였다. 최대한 관계식을 도출하려고 많은 시도를 하였다.

 

1일차부터  최대한의 스케줄을 dp 리스트에 추가하는 형식의 Bottom - up 방식으로 구현 하였다.

 

N = int(input())

date = []

for _ in range(N):

  T , P = map(int,input().split())

  date.append((T,P))

dp = [0] * (N+1)

# dp[i] 의 값은 이 날짜까지의 최대의 이익

for i in range(N):

  for j in range(i+date[i][0], N+1):

    if dp[j] < dp[i] + date[i][1]: # 이전까지의 이익 + 다음 날짜의 이익이 더 크면

      dp[j] = dp[i] + date[i][1] # 이익의 더 큰 값으로 바꾸어 줌

print(dp[-1]) # 인덱스의 마지막 값 출력

 

# 테스트 케이스 통과 후 제출 

 

# 느낀 점 

 

확실히 이 문제가 어떠한 알고리즘으로 풀어야 가장 효율적인지 판단을 충분히 가지는 시간이 필요하다고 생각하다.

 

그리고 머릿속에서만 생각하지 않고 그림 또는 손필기로 정리 했다면 빠르게 알고리즘을 파악할 수 있을거라고 생각한다.

 

코딩테스트에서는 시간이 촉박하므로 더욱 신중히 접근하는 습관을 길러야 겠다.