백준 / 퇴사 2 / 15486번 / Python

*문제 출처는 백준에 있습니다.

문제 제목: 퇴사 2 / 15486번 (골드 5단계)

문제 사이트: https://www.acmicpc.net/problem/15486

 

문제 설명

---

나의 풀이

n = int(input())  # 상담 기간

c = [list(map(int, input().split())) for _ in range(n)]

dp = [0] * (n + 1)  # 최대 수익을 저장할 DP 테이블

for i in range(n):
    t, p = c[i]  # 상담 기간, 금액

    # 이전 최대 수익 유지
    if i > 0:
        dp[i] = max(dp[i], dp[i - 1])

    # 상담을 진행할 수 있는 경우
    if i + t <= n:
        dp[i + t] = max(dp[i + t], dp[i] + p)

# 마지막 날까지의 최대 수익 계산
print(max(dp))

프로그램 로직은 다음과 같습니다. 하지만 파이썬의 입력 받는 속도가 느려서 시간 초과가 발생한 코드입니다.

import sys

# 입력을 최적화하여 한 번에 읽기
input = sys.stdin.read

data = input().split('\n')
n = int(data[0])  # 상담 기간

c = [list(map(int, line.split())) for line in data[1:n+1]]

dp = [0] * (n + 1)  # 최대 수익을 저장할 DP 테이블

for i in range(n):
    t, p = c[i]  # 상담 기간, 금액

    # 이전 최대 수익 유지
    dp[i] = max(dp[i], dp[i - 1] if i > 0 else 0)

    # 상담을 진행할 수 있는 경우
    if i + t <= n:
        dp[i + t] = max(dp[i + t], dp[i] + p)

# 마지막 날까지의 최대 수익 계산
print(max(dp))

위 코드는 입력 받는 속도를 향상 시킨 코드입니다!

---

※ 알아야 할 것

https://newkimjiwon.tistory.com/216

파이썬 입력 최적화(import sys, input())