[Python] BOJ 15486 : 퇴사2

요구사항 

1. 시간제한 2초
   1. N <= 1,500,000 이니 무조건 시간복잡도 작게
2. 메모리 512MB 
   1. 리스트 남발하지 않으면 될 거 같다. 
3. 상담을 적절히 해, 최대 수익을 구하자.

설계

1. 1일 부터 N일 까지 T와 P를 튜플로 받자.
2. 1차원 dp에 그 값들을 넣어주자. 
3. 2중 for문을 사용해서 적절히 넣어주자

구현

import sys
input = lambda: sys.stdin.readline().rstrip()

def max_advice_fee(advice):
    M = len(advice)
    dp = [0] * (M + 1)
    
    for i in range(1, M + 1):
        for j in range(1, M + 1):
            # j 는 날짜(N일) > i는 기준 날짜 
            # 예를 들어 기준 날짜 2일, T=5, P=20 이고 j는 1일 부터 7일까지 순회하면서 합보다 큰 지 비교
            if j > i + advice[i - 1][0]:
                # 상담료가 누적되어야함. 2일에 상담했으면 7일에 상담료와 같이 
                dp[j] = dp[j - advice[i-1][0]] + advice[j-1][1]
    return dp[M]

def main():
    N = int(input())
    advide = [tuple(map(int, input().split())) for _ in range(N)]
    
    print(max_advice_fee(advide))

if __name__ == "__main__":
    main()

# 입력
7
3 10
5 20
1 10
1 20
2 15
4 40
2 200
# 출력 결과
255

• 원한 의도와 다르게 나온다. 
• 아마 if문에서 내가 원한 의도와 다르게 걸리는 듯 하다.
• 의도한 바는 현재 2일차라고 했을 때, 걸리는 상담시간은 5일이다. 따라서 6일까지는 상담을 할 수 없다.
• 그렇기 때문에 7일부터 가능. 7 > 2 + 5 . 만족하지 않으니 넘어간다.  

import sys
input = lambda: sys.stdin.readline().rstrip()

def max_advice_fee(advice):
    M = len(advice)
    dp = [0] * (M + 1)

    for i in range(1, M + 1):
        # 현재 날짜에서 상담이 끝나는 날짜를 계산
        if i + advice[i-1][0] <= M + 1:
            # 상담을 하는 경우
            dp[i + advice[i-1][0] - 1] = max(dp[i + advice[i-1][0] - 1], dp[i-1] + advice[i-1][1])
        
        # 상담을 하지 않는 경우
        dp[i] = max(dp[i], dp[i-1])
    
    return dp[M]

def main():
    N = int(input())
    advice = [tuple(map(int, input().split())) for _ in range(N)]
    
    print(max_advice_fee(advice))

if __name__ == "__main__":
    main()