📌 [삼성 SW 역량 테스트 기출]
💡문제접근
- 코드로 구현하는 과정이 너무 힘들었다. 맨 뒤에서부터 가능한 경우를 확인하여 얻을 수 있는 최대 금액을 구했다.
- 테스트케이스에 나와있는 예제를 이용하자. 6, 7일차에 잡혀있는 상담의 소요 일수는 각각 4, 2일로 백준이는 8일차에 퇴사를 하기 때문에 상담을 할 수 없다. dp리스트에 0을 추가한 이유가 바로 이런 이유 때문이다.
- 4일차에 상담을 하고 5일차에 상담을 하면 이익을 얻을 수 있으므로 백준이가 일할 수 있는 시간 범위 내에서라면 dp리스트의 값을 비교해서 최댓값을 저장한다.
💡코드(메모리 : 30616KB, 시간 : 36ms)
N = int(input())
t = []
p = []
dp = []
for _ in range(N):
T, P = map(int, input().split())
t.append(T)
p.append(P)
dp.append(P)
dp.append(0)
for i in range(N-1, -1, -1):
if i + t[i] > N:
dp[i] = dp[i+1]
else:
dp[i] = max(dp[i+1], dp[i+t[i]] + p[i])
print(dp[0])
💡소요시간 : 2h