111. [삼성기출7]Python 백준 14501 번 퇴사 자세한 설명

안녕하세요 코딩하는 덕구입니다.

백준 14501 번 퇴사 입니다.

https://www.acmicpc.net/problem/14501

14501번: 퇴사

 

먼저 백준 14501 번 퇴사 파이썬 정답 코드입니다. 설명은 아래에 있습니다.

N = int(input())
T = [] #걸리는 시간
P = [] #버는 돈
dp = [0 for _ in range(N+1)] #가장 큰 이익

for _ in range(N):
    t, p = map(int, input().split())
    T.append(t)
    P.append(p)

def bottom_up():
    for i in range(N):
        for j in range(i + T[i], N+1):
            dp[j] = max(dp[j], dp[i] + P[i])
    print(dp[-1])

def top_down():
    for i in range(N-1, -1, -1):
        if i + T[i] > N:
            dp[i] = dp[i+1]
        else:
            dp[i] = max(dp[i+1], dp[i + T[i]] + P[i])
    print(dp[0])

top_down()

 

문제 요약

백준이는 퇴사일 전까지 상담을 진행합니다.

상담은 매일 있고, 각 상담이 끝나는 날짜와 이익은 다릅니다.

퇴사일 전까지 상담이 끝나야만 상담을 진행할 수 있습니다.

이때 얻을 수 있는 최대 이익을 구해서 출력합니다.

 

문제 접근

dp문제 입니다.

리스트를 이용하여 i번째 날짜의 최대이익을 저장하고

그것을 통해 i+1 번째 날짜의 최대이익을 계속 업데이트 하며

불필요한 반복을 줄이고 얻을 수 있는 최대 이익을 구합니다.

 

Python 코드 구현

 먼저 퇴사일과 각 상담 별 상담 소요시간, 이익을 입력받고 저장합니다.

가장 큰 이익을 구하기 위한 리스트 dp또한 구현합니다.

N = int(input())
T = [] #걸리는 시간
P = [] #버는 돈
dp = [0 for _ in range(N+1)] #가장 큰 이익

for _ in range(N):
    t, p = map(int, input().split())
    T.append(t) #상담 소요 시간
    P.append(p) #이익

 

먼저 bottom_up 방식입니다.

def bottom_up():
    for i in range(N):
        for j in range(i + T[i], N+1):
            dp[j] = max(dp[j], dp[i] + P[i])
    print(dp[-1])

 

1일부터 N일 까지 모든 날짜를 돌면서 (0부터 N-1 일까지지만 모든 리스트 저장을 0으로 했기 때문에 같습니다.)

for i in range(N):

 

상담이 가능한 모든 날짜를 확인하며

for j in range(i + T[i], N+1):

 

해당 날짜에 상담을 진행하는 것이 (dp[i] + P[i]) 지금까지의 이익보다 크다면 업데이트합니다. 

dp[j] = max(dp[j], dp[i] + P[i])

 

모든 탐색이 끝나면 마지막 index를 출력합니다.

print(dp[-1])

 

 다음은 top_down 방식입니다. 뒤에서부터 dp를 채워 결국 dp[0]에 최대 이익이 저장됩니다.

def top_down():
    for i in range(N-1, -1, -1):
        if i + T[i] > N:
            dp[i] = dp[i+1]
        else:
            dp[i] = max(dp[i+1], dp[i + T[i]] + P[i])
    print(dp[0])

 

N부터 0까지 돌면서

for i in range(N-1, -1, -1):

 

만약 상담 기간이 퇴사일을 넘기면 상담을 진행하지 않고,

if i + T[i] > N:
    dp[i] = dp[i+1]

 

상담 기간이 퇴사일을 넘기지 않는다면

지금까지의 이익과(dp[i+1]) 지금 날짜에 상담을 진행하는 것 중 더 이익이 큰 것을 저장합니다.

else:
    dp[i] = max(dp[i+1], dp[i + T[i]] + P[i])

 

0번 index를 출력하면 됩니다.

print(dp[0])

 

파이썬 백준 14501 번 퇴사 최종 코드입니다. 

N = int(input())
T = [] #걸리는 시간
P = [] #버는 돈
dp = [0 for _ in range(N+1)] #가장 큰 이익

for _ in range(N):
    t, p = map(int, input().split())
    T.append(t)
    P.append(p)

def bottom_up():
    for i in range(N):
        for j in range(i + T[i], N+1):
            dp[j] = max(dp[j], dp[i] + P[i])
    print(dp[-1])

def top_down():
    for i in range(N-1, -1, -1):
        if i + T[i] > N:
            dp[i] = dp[i+1]
        else:
            dp[i] = max(dp[i+1], dp[i + T[i]] + P[i])
    print(dp[0])

top_down() #or bottom_up()

백준 14501 번 퇴사 자세한 설명 및 Python 코드였습니다.

감사합니다.