BOJ #14501 퇴사 python

💡Github URL

: https://github.com/hansun-hub/2025-algorithm-study/commit/c8d2a247558a50f2e89e5d4ca6ebc7800c898082

 

💡문제에서 구해야 할 것

문제 조건 :

• 시간과 pay가 주어지면 퇴사 전까지 최대의 돈을 벌기 위해 받을 수 있는 상담을 고려해 최대 pay의 합을 구하라

 

💡알고리즘 설계

• 스케쥴을 입력받고 dp[0] 테이블 N+2 크기로 생성
• 뒤에서부터 dp 값 갱신하며 상담이 가능한 날, 불가능한 날 if, else 구문으로 분기

 

💡코드

def max_profit(N, schedule):
    dp = [0] * (N + 2)  # N+1까지 필요하므로 N+2 크기 할당

    # 뒤에서부터 dp 갱신
    for day in range(N, 0, -1):
        time, pay = schedule[day - 1]  # 상담 기간, 이익
        next_day = day + time  # 상담이 끝나는 날

        if next_day <= N + 1:  # 상담 가능
            dp[day] = max(dp[day + 1], pay + dp[next_day])
        else:  # 상담 불가능
            dp[day] = dp[day + 1]

    return dp[1]  # 1일부터 시작할 때 최대 이익 반환

# 입력 처리
N = int(input())
schedule = [tuple(map(int, input().split())) for _ in range(N)]
print(max_profit(N, schedule))

 

💡시간복잡도

O(n)

 

💡 틀린 이유 & 틀린 부분 수정

어떻게 접근할 생각조차 못했다 ^ㅁ^

 

💡 다른 풀이 or 기억할정보

schedule = [tuple(map(int, input().split())) for _ in range(N)]

• 튜플(tuple)

변경할 수 없는(immutable) 순서가 있는 데이터 구조

리스트(list) 와 비슷하지만, 한 번 생성하면 값을 수정, 추가, 삭제 불가

→ 튜플은 변경할 필요가 없는 데이터를 저장할 때 사용 시 유용

→ 튜플이 리스트보다 상대적으로 빠름 🆗

 

 

• DP 테이블의 역할

dp = [0] * (N + 2)

동적 계획법(DP)을 사용할 때 중간 결과를 저장하는 배열

이 테이블을 활용하면 이전에 계산한 값을 재사용하여

중복 계산을 방지하고 최적의 해답을 빠르게 찾을 수 있어.

 

 

 

• 이번 문제에서 DP 테이블의 역할

이 문제에서는 dp[i]가 i번째 날부터 퇴사일까지

얻을 수 있는 최대 이익을 저장하는 역할

 

 

• dp 테이블이 n+2 까지 필요한 이유 ?

if next_day <= N + 1:  # 상담 가능
      dp[day] = max(dp[day + 1], pay + dp[next_day])
else:  # 상담 불가능
      dp[day] = dp[day + 1]
     

가장 마지막 날을 계산할 때 day+1 계산을 위해서 , 어짜피 0으로 초기화 해줌