[BOJ] 14501 퇴사

1. 문제

• N+1일 째 퇴사

• 남은 N일 동안 최대한 많은 상담

• 상담 기간 Ti

• 상담 시 받을 수 잇는 금액 Pi

  • 예

    

    - 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)
  • Ti Pi (1일부터 N일까지 순서대로, 1 ≤ Ti ≤ 5, 1 ≤ Pi ≤ 1,000)
• 출력 : 백준이 얻을 수 있는 최대 이익

2. 풀이

• DP

  • n번째 일에 최대 이익을 구하기 위해서는 (i일 전날의 최대 이익 + i일의 금액) 중 최대 이익을 구해야 함

  • 1~7일을 차례대로 선택해서 그날의 수익을 받았을 때의 최대 수익들을 차례대로 구하면 N+1째 날에 얻을 수 있는 최대 수익을 구할 수 있다.

    

    	1일	2일	3일	4일	5일	6일	7일
    1일 상담 진행시	0	0	0	10	0	0	0
    1일 + 4일				10	30	0	0
    1일 + 4일 + 5일				10	30	0	45
    1일 + 5일				10	10	0	25

  • 1일 + 6일 상담 진행 시 상담이 끝나면 6 + 4일 = 10일이므로 해당 조합으로는 상담 진행이 불가하다

  • 이런 방식으로 i번째 일의 상담을 진행할 경우, 현재 날짜+i일 이후부터 n일까지의 최댓 수익을 순차적으로 구하여 최종적으로 백준이가 얻을 수 있는 최대 수익을 구할 수 있다.

3. 코드

def solution():

  N = int(input())
  T = []
  P = []
  
  for _ in range(N):
    t, p = map(int, input().split())
    T.append(t)
    P.append(p)
  
  day = [0] * (N + 1)
  
  for i in range(N):
    for j in range(i + T[i], N + 1):
      if day[j] < day[i] + P[i]:
        day[j] = day[i] + P[i]
        
  print(day[-1])

solution()

+α

• DP 다시 연습하기
• 재귀적 + 반복적인 구조를 찾고 그것을 코드로 구현하는 것 연습하기