[BOJ]1548_퇴사2

 

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

15486번: 퇴사 2

 

 

📌풀이

• 이 문제를 풀기 위해 가장 도움을 준 부분이 예시4이다. 

예제 입력 4 복사

10
5 50 #1일차
4 40 #2일차
3 30 #3
2 20 #4
1 10 #5
1 10 #6
2 20 #7
3 30 #8
4 40 #9
5 50 #10

예제 출력 4 복사

90

• 예시4를 보면서 어떤식으로 생각하면 90이 나올까? 라고 생각하던 차에 1일차에 5일을 일하고 받는 수당이 50일 때
• 5일을 일한 그 다음 6일차에 하루를 더 추가하여 10을 받아 => 받는 수당이 60이 된다. 
• 6일차 이후에 남는 시간들을 살펴보니 7일차와 8일차 둘다 퇴사일(n)까지 근무 가능하기 때문에 둘 중 어느날을 고르냐에서 문제가 발생했다. 
• 사실 답은 "당연히도" 둘중에 돈을 더 많이 주는 곳을 선택할 것이다. 

이러한 생각의 흐름을 코드로 바꿀 수 있을 것 같다는 생각이 떠올라 

바로 코드로 옮겨 적었다. 

• 우선, 내가 명명한 1일차와 for문에서의 인덱스를 매칭시키기위해 for문은 총 (n+1)번을 돌린다.
• 또한, 각각의 날짜에 일하고 받는 수당(가치)을 갱신하기 위한 테이블의 length도 (n+1)로 설정한다.
• 두 일차 중 퇴사일까지 근무가 가능한지 여부를 확인하고 가능하면 -> 이전 수당과 내가 그 일을 하고 나서 받을 수 있는 돈을 비교한다. 
  • 근무 가능 여부 
    • 현재 날짜 + 근무 기간 - 1 = i + n - 1
    • -1을 해줌으로써 일을 시작한 당일부터 포함시킴
  •  이전 수당과 내가 그 일을 하고 나서 받을 수 있는 돈을 비교

end_day = i + time[i] - 1
if end_day <= n:
	table[end_day] = max(table[end_day], table[i - 1] + price[i])

• 여기까지 생각을 하고 나서 걸리는 것이 이제 여기서 중요한 것은
• 조건을 따지기 전에 table의 요소를 이전에 적립한 수당 중 가장 최대의 값을 갱신해둔다. 

이를 종합한 코드는 아래와 같다. 

📌정답

import sys

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

n = int(input())
time, price = [0]*(n+1), [0]*(n+1)

for i in range(1, n + 1):
    time[i], price[i] = map(int, input().split())

table = [0]*(n+1)

for i in range(1, n + 1):

    table[i] = max(table[i], table[i - 1])  
    
    end_day = i + time[i] - 1  #일 끝날 날
    
    if end_day <= n:  # 일이 퇴사 전까지 끝나는 경우
        # 전 날 얻은 수익과 일을 할 경우 얻을 수당을 비교
        table[end_day] = max(table[end_day], table[i - 1] + price[i])
print(max(table))