[백준] 14501 - 퇴사 [Python(파이썬)]

'삼성 SW 역량 테스트' 기출 문제 입니다. 😀

문제 👉 14501번: 퇴사

1. 문제

1. 상담 일정표는 상담 기간과 상담 금액으로 이루어져 있다.
2. N일 동안 적절한 상담 조합을 통해 구할 수 있는 최대 금액을 출력한다.

2. 풀이

DP(Dynamic Programming)을 이용한 문제 풀이

1. 크기가 N인 DP 배열 생성
2. 당일 상담이 퇴사 전에 가능할 경우 상담 선택한다.
3. 당일 이전에 상담이 끝나는 날 중 보상이 가장 큰 날의 보상을 당일 보상에 더한다.
4. DP배열에서 가장 보상이 큰 날을 return

3. 코드

def solution(): 
    N = int(input()) 
    L = [list(map(int, input().split())) for _ in range(N)]
    dp = [0]*N # N일 동안 선택할 수 있는 최대 금액

    for i in range(N):
        if i + L[i][0] <= N: # 퇴사 전에 가능한 상담일 경우
            dp[i] = L[i][1] # 당일 상담의 금액을 저장
            for j in range(i):
                if j + L[j][0] <= i: # 이전의 상담이 오늘 전에 가능할 경우
                    dp[i] = max(dp[i], dp[j]+L[i][1]) # (이전의 상담 금액 + 당일 상담 금액)의 최대 값 선택
    return max(dp)
print(solution())

• 결과는 64 ms 나왔다.

---

References

•  

---

🏋🏻 개인적으로 공부한 내용을 기록하고 있습니다.
잘못된 부분이 있다면 과감하게 지적해주세요!! 🏋