백준 14501 - 퇴사 파이썬

문제 

14501번: 퇴사

유명한 퇴사 짤

 

해결 코드 

# 변수 입력 받기
n = int(input()) # 총 상담 일수
arr = [list(map(int, input().split())) for _ in range(n)] # 각 상담 일정 정보를 담은 리스트

# DP를 위한 초기화
dp = [0 for _ in range(n+1)] # 각 상담 일자별 최대 수익

# DP 계산
for i in range(n-1, -1, -1): # 역순으로 탐색
    # 현재 상담을 진행할 수 없는 경우
    if i + arr[i][0] > n:
        dp[i] = dp[i+1] # 상담을 하지 않음
    # 현재 상담을 진행할 수 있는 경우
    else:
        # 상담을 하는 경우와 하지 않는 경우 중 더 큰 값 선택
        dp[i] = max(dp[i+1], arr[i][1]+dp[i+arr[i][0]])

# 결과 출력
print(dp[0]) # 첫째 날부터 상담을 시작하므로, dp[0]이 전체 수익의 최댓값

 

- 리스트 arr의 각 원소는 [상담에 걸리는 기간, 해당 상담의 수익] 형태

 

- for문에서 역순으로 탐색하는 이유는, 이전에 계산한 값들을 이용하여 뒤에서부터 최대 수익을 계산하기 때문  

 

- 마지막으로, dp[0]을 출력하여 첫째 날부터 상담을 시작하며 전체 수익의 최댓값

 

- 위 문제는 Top own방식으로 풀이 

 

- Top-down

전체 문제를 풀기위해서 작은 문제를 풀이한 재귀함수를 호출하여 풀이 

주로 재귀함수와 Memoization 활용

Python에서는 시간초과가 발생할 가능성이 높음

 

- Bottom-up

문제를 크기가 작은 부분부터 차례대로 풀면서, 크기를 조금씩 키워나가는 형식

주로 반복문과 Memoization 활용

dp문제를 만나면 바텀업, 반복문으로 푸는 것이 오버헤드 가능성을 낮춰 더 좋은 풀이일 가능성이 높음