[백준14501] / 퇴사 - DP

 

백준14501

 

푼 날짜 : 2024.10.08

푼 문제 : [14501] / 퇴사

사용한 언어 : python

알고리즘 : DP

 

 

접근 방법 :

 

1) 상담횟수와 금액 배열을 따로 만들자!

 

금액이 높다고 출력 X

상담을 제일 많이 한 날의 금액을 출력 O

 

따라서 두 값을 적절히 저장할 배열이 필요하다.

 

2) 계산이 불가능 한 경우를 먼저 지우자! 

• 오늘부터 상담을 시작했을 때 퇴사 전 끝내지 못할 경우 (i + lst[i][0] > N)
  • 예를 들어 8일에 상담이 끝나는데 7일에 2일이 걸리는 상담은 불가능하다. 
• 오늘 기준으로 이전 상담을 완료하지 못한 경우 (j + lst[j][0] > i)
  • 예를 들어 오늘이 5일인데 2일에 4일짜리 상담을 했다면 오늘 기준으로 상담이 완료되지 않았으므로 상담 불가.

3) 계산 시에는 오늘 날짜를 기준으로 해서 이전 날짜들을 확인하며 상담을 제일 많이 한 날과 비교해서 상담횟수(cnt)를 증가시키고 오늘 금액을 더해서 업데이트 해준다.

if dp[i] < dp[j]+lst[i][1]:
    dp[i] = dp[j]+lst[i][1]
    cnt [il = cnt[j]+1

 

 

4) 최종적으로 cnt 배열(상담횟수 저장 배열)을 확인 했을 때 상담을 제일 많이 한 날의 금액을 출력한다.

 

 

코드 :

import sys

N = int(sys.stdin.readline())
lst = []
for _ in range(N):
    t, p = map(int, sys.stdin.readline().split())
    lst.append((t, p)) # (t = 상담에 걸리는 일수, p = 상담 금액) => 튜플로 저장

dp = [0 for _ in range(N)]
cnt = [1 for _ in range(N)]

# 초기값 설정
dp[0] = lst[0][1] if lst[0][0] <= N else 0
cnt[0] = 1 if lst[0][0] <= N else 0

for i in range(1, N):
    if i+lst[i][0] > N: continue # 퇴사 전 상담 마무리가 불가능한 경우는 패스
    
    dp[i] = lst[i][1]
    for j in range(i):
        if j+lst[j][0]> i: continue # 오늘이 지나서 끝나는 상담일은 패스 (상담시작+상담진행 > 오늘)
        if dp[i] < dp[j]+lst[i][1]: 
            dp[i] = dp[j]+lst[i][1]
            cnt[i] = cnt[j]+1

ans = 0
idx = -1
for i in range(len(cnt)):
    if idx <= cnt[i]: # 카운트 값이 같거나 더 큰 경우 (상담을 더 많이 할 수 있는 경우)
        idx = cnt[i]
        ans = max(ans, dp[i])

print(ans)

 

 

 

내가 참고했던 반례:

1
1 100

#ans 100

 

=> 이 경우에는 초기값 설정을 잘 확인해줘야 한다.

99% ? 그 즈음에서 틀릴 경우 이 문제일 가능성이 높다! 

 

2
3 100
1 2

#ans 2

3
5 50
3 30
1 10

#ans 10

 

=> 두 경우에도 퇴사 전에 상담 완료가 가능한 지를 잘 판별해야한다.

 

 

 

반례를 찾고 Hidden case에 맞게 코드를 수정하는 것은 깊은 사고력을 요하는 일이다.

앞으로도 꾸준히 꼼꼼하게 연습해야겠다. \_へ(▭-▭)✨