백준 삼성 코딩 기출 문제 - 퇴사 python

백준 삼성 코딩 기출 문제 - 퇴사 python

출처 : BAEKJOON ONLINE JUDGE

퇴사 (https://www.acmicpc.net/problem/14501)

문제 설명

퇴사를 진행행하려 하는는데 N+1일 째 되는날 퇴사를 하기 위해서 N일 동안 많은 상담을 하려고 합니다.

상담을 완료하는데 걸리는 시간 T와 상담을 했을 때 받을 수 있는 금액 P를 보고, 퇴사 전까지 최대 수익을 구하는 문제입니다.

문제 풀이

각 팀의 회의 시작 시간과 회의 시간이 정해진 타임 테이블에서 최대한 많은 회의를 잡으려고 하는 dynamic programming과 비슷합니다. dynamic programming으로 풀면 쉽습니다.

[1] 입력을 받습니다. 입력받은 n으로 t와 p라는 배열을 선언하고 들어오는 입력에 배열을 넣습니다.

n = int(input()) t, p = [0]*n, [0]*n for i in range(n):     t[i], p[i] = map(int, input().split())

[2] dynamic programming 방식으로 진행합니다. dp라는 배열을 생성하고 이 배열의 원소들은 해당 날에 받을 수 있는 최대의 보상을 저장하게 됩니다. 

[3] dp는 현재 받게 될 보상과 내일 받게 될 보상을 비교합니다. 최대 수익을 구하기 때문에, 현재 받게 될 금액이 훨씬 더 클 경우 다음날 번 돈은 현재 금액으로 저장합니다.

[4] 현재 기준으로 T일 이후에 받게 될 보상이 상담을 수행해서 받게 될 금액(P)보다 적다면 현재 금액(dp) + 상담 금액(P)로 저장합니다.

for i in range(n):     if dp[i] > dp[i + 1]: # 현재가 다음날보다 보상이 높다면         dp[i + 1] = dp[i] # 다음날 보상은 현재로             if dp[i + T[i]] < dp[i] + P[i]: # T일 후에 받게될 금액이 상담을 해서 받게될 금액 보다 적다면         dp[i + T[i]] = dp[i] + P[i] # 상담을 진행할 금액과 현재의 금액을 넣어 받게될 수익 저장

풀이 과정으로 첫 번째 케이스를 풀어 보면 다음과 같습니다.

figure reference (https://www.acmicpc.net/problem/14501)

0번째 인덱스(1일) : dp[0] = 0, T[0] = 3, P[0] = 10 이므로 dp[0+3] = dp[3] = dp[0]+P[0] = 0 + 10

1번째 인덱스(2일) : dp[1] = 0,T[1] = 5, P[1] =20 이므로 dp[1+5] = dp[6] = dp[1]+P[1] = 0  + 20

2번째 인덱스(3일) : dp[2] = 0, dp[3] = 10, T[2] = 1, P[2] = 10 이므로 dp[2+1] = 10
- 위의 코드 2개 조건다 만족하지 않으므로 넘어갑니다.

3번째 인덱스(4일) : dp[3] = 10, T[3] = 1, P[3] = 20이므로,
- 첫 번째 조건에서 dp[4] = 10으로 저장
- 두 번째 조건에서 상담을 수행하면 dp[3+1] = dp[4] =  dp[3] + P[3] = 10 + 20 = 30 

 - 따라서, dp = [0, 0, 0, 10, 30, 0, 20, …]

4번째 인덱스(5일) : dp[4] = 30, T[4] = 2, P[4] = 15

 - 첫 번째 조건에서 dp[5] = 30

 - 두 번째 조건에서 dp[4+2] = dp[6] = dp[4] + P[4] = 45  

 - 따라서, dp = [0, 0, 0, 10, 30, 30, 45, …]

5번째 인덱스(6일) : dp[5] = 30, T[5] = 4, P[5] = 40

 - 첫 번째 조건에서는 현재가 다음날 보상보다 적습니다.

 - 두 번째 조건에서는 dp[5+4] = dp[9] = dp[5] + P[5] = 70

6번째 인덱스(7일): dp[6] = 45, T[6] = 2, P[6] = 200

 - 첫 번째 조건에서 dp[7]은 0이기 때문에 dp[7]에 현재 보상인 45가 저장 dp[7] = 45

 - 두 번째 조건에서 dp[6+2] = dp[8] = dp[6] + P[6] = 45 + 200 = 245

[5] dp 배열은 해당날까지 받게될 최대 수익을 저장했기 때문에 7일날 수익을 살펴보면 됩니다. dp[7]

즉 dp[n]을 출력하면 됩니다.

전체 코드

n = int(input()) t, p = [0]*n, [0]*n for i in range(n):     t[i], p[i] = map(int, input().split())         dp = [0]*25 for i in range(n):     if dp[i] > dp[i+1]: # 현재가 다음날보다 보상이 높다면         dp[i+1] = dp[i] # 다음날 보상은 현재로     if dp[i+t[i]] < dp[i] + p[i]: # T일 후에 받게될 금액이 현재의 보상보다 높다면         dp[i+t[i]] = dp[i] + p[i] # T일후에 보상을 넣는다.         print(dp[n])