백준 15486 [퇴사 2] 파이썬

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

퇴사 1

 

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

퇴사 2

# 백준 15486 퇴사 2
import sys
from collections import defaultdict

# 상담 가능한 총 일 수 N 입력
N = int(sys.stdin.readline())

# 각 날짜마다 걸리는 상담 시간(T)과 받을 수 있는 금액(P) 저장
T = []  # 상담에 걸리는 일 수
P = []  # 상담 시 받을 수 있는 금액

# end_days[i]는 i일에 끝나는 상담들의 시작 인덱스를 저장
end_days = [[] for _ in range(N + 1)]

# dp[i]는 i일 기준으로 얻을 수 있는 최대 이익
dp = [0 for _ in range(N + 1)]

# 입력 받으면서, 상담이 기간 내에 끝날 수 있으면 end_days에 기록
for i in range(N):
    st, c = map(int, sys.stdin.readline().split())
    T.append(st)
    P.append(c)
    if T[i] + i < N + 1:
        end_days[T[i] + i].append(i)  # i번째 날 시작한 상담이 끝나는 날짜에 기록

# dp 배열 채우기
for i in range(N + 1):
    # i일에 끝나는 상담들을 확인하며 최대 이익 갱신
    for ind in end_days[i]:
        if ind + T[ind] == i:
            dp[i] = max(dp[i], dp[ind] + P[ind])
    
    # 이전 날까지의 최대 이익이 더 클 경우 갱신 (상담을 하지 않는 경우)
    if i >= 1 and dp[i] < dp[i - 1]:
        dp[i] = dp[i - 1]

# 전체 기간 동안 얻을 수 있는 최대 수익 출력
print(max(dp))

 

퇴사1을 풀고나서 2도 같은 원리로 풀면되지 않을까 생각했는데, 그렇지 않았다. 시간 복잡도를 고려해야됐었다..

for문을 2번 도는것이 아니라, 현재 날짜(i번째 날)에 끝나는 상담을 배열에 넣어서, 그 경우만 고려하였다.

DP 갈 길이 멀다..

 

미--------------------------친 GPT

FOR문을 한 번만 썼다.

# GPT 코드
import sys
input = sys.stdin.readline  # 빠른 입력을 위해 sys.stdin.readline 사용

# 총 상담 일수 N 입력
N = int(input())

# 상담 기간(T)과 수익(P)을 담을 리스트
T = []
P = []

# 각 날짜별 상담 기간과 수익 입력
for _ in range(N):
    t, p = map(int, input().split())
    T.append(t)
    P.append(p)

# dp[i]는 i번째 날부터 마지막 날까지 얻을 수 있는 최대 수익
# N+2로 잡는 이유는 dp[N+1]까지 접근할 수 있도록 하기 위해 (종료일이 N+1일일 수 있음)
dp = [0] * (N + 2)

# N일부터 1일까지 거꾸로 계산
for day in range(N, 0, -1):
    end_day = day + T[day - 1]  # 오늘 시작하는 상담이 끝나는 날

    if end_day <= N + 1:
        # 오늘 상담을 하면 얻을 수 있는 수익 vs 오늘 상담을 하지 않고 다음 날로 넘긴 수익
        dp[day] = max(P[day - 1] + dp[end_day], dp[day + 1])
    else:
        # 오늘 상담을 하면 퇴사일(N+1일)을 넘기므로 상담 불가 → 그냥 다음 날로 넘김
        dp[day] = dp[day + 1]

# 1일부터 시작했을 때의 최대 수익 출력
print(dp[1])