33_퇴사

14501번: 퇴사

 

DP 문제다.

상담을 진행했을 때, 받을 수 있는 최대 이익을 출력하면 되는 문제.

 

처음에 그냥 떠오른 점화식은 다음과 같다.

time와 price 리스트가 있을 때, 

dp[i+time[i]] = max(dp[i] + price[i], dp[i+time[i])

 

이런 식으로 점화식을 만들어주면, 답이 나오는 것 같았다.

물론 돌려보니 실패했다.

반례를 찾다보니, 통과하지 못하는 반례르 발견했다.

 

4

3 1

1 100

2 100

1 1000

 

이 반례의 정답은 1100인데 1001이라는 잘못된 답을 뱉어냈다.

 

dp테이블을 손수 직접 돌아보면서, 잘못된 점을 찾았고, 새로운 점화식을 만들었다.

dp[i+time[i]] = max(max(dp[:i+1]) + price[i], dp[i+time[i]])

 

dp[i] = i-1번째 날짜까지 상담을 진행한 후, 이익의 최댓값

즉, dp[8]은 7번째 날짜까지 상담을 진행한 후, 이익의 최댓값을 의미한다.

 

이 점화식에서 바뀐 부분은 굵게 표시된 부분이다.

위 부분을 바꾼 이유는 dp 테이블을 갱신하다가 만약 특정 날짜의 dp테이블을 확인했을 때, 0인 경우도 존재하고, 

또한 0이 아니더라도, 그 동안 만든 dp 테이블의 최댓값에다가 그날 상담을 진행할 경우, 얻을 수 있는 이익을 더하는 것이 맞다.

 

즉,

dp[i+time[i]] = (i - 1)+time[i]번째 날까지 상담을 진행한 후의 최대 이익

max(dp[:i+1]) + price[i] = i-1번째 날까지의 최대이익 + i번째 날 상담을 진행할 경우 얻는 이익

이 2가지를 비교해서 더 큰 값을 dp[i+time[i]]에 갱신해준다.

 

 

풀이 코드

# 14501번: 퇴사

n = int(input())
time = [0] # 상담하는데 필요한 기간
price = [0] # 상담 이익

dp = [0] * 21 # dp 테이블

# 상담기간, 상담이익 추가
for _ in range(n):
    t, p = map(int, input().split())
    time.append(t)
    price.append(p)


# dp 테이블 갱신
for i in range(1, n+1):
    dp[i+time[i]] = max(max(dp[:i+1])+price[i], dp[i+time[i]])

# print(dp[1:])
print(max(dp[:n+2]))

 

---

다른 풀이

 

책에서는 약간 다르게 풀었다.

dp 테이블을 갱신할 때, 뒤쪽 날짜부터 거꾸로 확인하는 방식으로 접근하여 해결하는 것이다.

 

위 백준 링크에 첫번째 예시의 경우를 보자.

만약 1일차에 상담을 진행한다고 하자.

이 경우 3일에 걸쳐서 상담을 진행해야 하므로 결과적으로 4일부터 상담을 진행할 수 있다.

그러므로 1일차에 상담을 진행할 경우 얻을 수 있는 최대 이익은 "1일차의 상담 금액 + 4일부터의 최대 상금 금액"이다.

이러한 원리를 이용해, 뒤쪽부터 거꾸로 계산해서 문제를 해결할 수 있다.

 

뒤쪽부터, 매 상담에 대해 

현재 상담 금액 -> p[i]

현재 상담을 마친 일자부터의 최대 이윤 -> dp[i+time[i]]

를 더한 값을 계산하면 된다.

이후에 계산된 각각의 값 중에서 최댓값을 출력하면 된다.

 

여기서 dp[i]는 i번째 날부터 마지막 날까지 낼 수 있는 최대 이익이다.

 

점화식은 다음과 같다.

dp[i] = max(dp[i + time[i]) + price[i], max_value)

 

이때, max_value는 뒤에서부터 계산할 때, 현재까지의 최대 상담 금액에 해당하는 변수다.

 

 

풀이 코드

# 14501번: 퇴사

# 풀이 2.
n = int(input())
time = [] # 상담하는데 필요한 기간
price = [] # 상담 이익

dp = [0] * 21 # dp 테이블

# 상담기간, 상담이익 추가
for _ in range(n):
    t, p = map(int, input().split())
    time.append(t)
    price.append(p)
max_value = 0

# 리스트를 뒤에서부터 거꾸로 확인
for i in range(n-1, -1, -1):
    t = time[i] + i
    # 상담이 기간 안에 끝나는 경우
    if t <= n:
        # 점화식에 맞게, 현재까지의 최고 이익 계산
        dp[i] = max(price[i] + dp[t], max_value)
        max_value = dp[i]
    # 상담이 기간을 벗어나는 경우
    else:
        dp[i] = max_value

print(max_value)

 

뒤에서부터 계산한다는 것은 생각하지 못했다.

dp 문제는 이런 방식으로도 풀 수 있다는 것을 알았던 문제였다.