[Python] BOJ 14501 - 퇴사

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

14501번: 퇴사

# 2017년 상반기 삼성 SW 역량 테스트 기출문제이다.

# DP문제치곤, 그렇게 어렵지 않았다.

 

# N일부터 1일까지 앞으로 가며 dp테이블을 갱신하는 코드:

  1. 우선 arr[i][0] + i (현재 일수 + 상담에 걸리는 일수)가 N보다 크면 상담을 못하므로 dp[i]에 m을 넣어준다.

  2. N보다 작을때

     dp[i] = max(현재 상담을 완료하면 받는 금액(arr[i][1]) +

                                  현재 상담을 마친 일자부터의 최대 이윤(dp[arr[i][0] + i], m) 으로 갱신해준다.

     (m = 마지막날부터 계산할 때 현재까지의 최대 상담 금액)

     그리고, m에 dp[i]를 넣어준다.

  3. 마지막으로 dp의 최댓값을 출력해준다.

 

# N일부터 1일까지 앞으로 가며 dp테이블 갱신하는 코드

import sys
input = sys.stdin.readline
N = int(input())
arr = []
for _ in range(N):
	t, p = map(int,input().split())
	arr.append([t, p])
dp = [0] * (N+1)
m = 0

for i in range(N-1, -1, -1):
	if arr[i][0] + i <= N:
		dp[i] = max(arr[i][1] + dp[arr[i][0] + i], m)
		m = dp[i]
	else:
		dp[i] = m
print(max(dp))

=========================================================================

# 1일부터 N일까지 dp테이블을 갱신하는 코드도 위의 코드랑 진행방향이 다를 뿐, 

   알고리즘은 똑같다.

 

# 1일부터 뒤로 가며 dp테이블 갱신하는 코드

N = int(input())
table = []
dp = [0] * N
for _ in range(N):
	a, b = map(int,input().split())
	table.append([a,b])

for k in range(N):
	if k + table[k][0] <= N:
		dp[k] = table[k][1]
		for i in range(k):
			if table[i][0] + i <= k:
				dp[k] = max(dp[k], dp[i] + table[k][1])
print(max(dp))

(solved.ac 티어: 실버 4)

 

# 아래코드는 이중 for문이어서 시간이 더 걸릴줄 알았는데, 걸린시간이 똑같아서 의외였다.