[백준/14501] 퇴사

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

14501번: 퇴사

---

 고려할 조건이 많아서 생각보다 만점을 받기가 어려운 문제였습니다. 만약 상담 시작 일자에 기간을 더해서 '종료 일자'를 만들어 관리하면 코드 작성이 더 수월한 것 같습니다. 풀이에 있어 고려해야할 사항은 다음과 같습니다.

---

1) 종료 일자가 현재 고려 중인 상담 일자 이하인 경우에만 수익을 더할 수 있습니다. 예를 들어 현재 고려 중인 날짜가 5일의 상담인데, 3일 째의 상담의 종료 일자가 7일이라면, 3일째의 일자를 고려하지 않습니다.

2) 종료 일자가 퇴사 일자 이상이게 되면 고려하지 않습니다. 이것은 첫번째 상담날도 마찬가지입니다.

---

 N이 15이하의 정수로 주어지기 때문에 3중 반복문을 쓰더라도 문제 없으며, 시간 제한이 2초로 넉넉하기 때문에 사실상 아이디어만 풀 수 있다면 어떻게든 풀이 가능한 문제입니다. 아래 코드같은 경우는 시간복잡도가 O(N^2)입니다.

 

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

end = []
price = []

for i, (t, p) in enumerate(array):
    end.append(t + i)
    price.append(p)

table = [0] * n

for i in range(0, n):
    if end[i] > n:
        continue
    tmp = [0]
    for j in range(0, i):
        if end[j] <= i:
            tmp.append(table[j])
    table[i] = max(tmp) + price[i]

print(max(table))

 

 위의 코드에서는 end와 price를 나누어 관리했습니다. 이렇게 할 경우 인덱싱을 통해 각 상담의 종료일자와 가격에 빠르게 접근할 수 있습니다. 또한 인덱싱의 편의상 가장 처음의 일자를 0으로 고려하고 진행했습니다.

end = []
price = []

for i, (t, p) in enumerate(array):
    end.append(t + i)
    price.append(p)

 이후 테이블을 일자만큼 초기화하고, 첫번째 상담일자부터 순회하면서 테이블을 업데이트합니다. 핵심이 되는 점화식은 DP_n = max(DP_end<=n) + a_n입니다. 즉, 첫번째 날부터 차례대로 고려하되, 이전 일자 중 종료 일자가 현재 일자 이하인 것들 중 가장 돈을 많이 버는 경우에 현재 가격을 더합니다. 여기서는 조건문을 이용해서 tmp 변수에 조건에 맞는 값을 넣어주었습니다.

 

table = [0] * n

for i in range(0, n):
    if end[i] > n:
        continue
    tmp = [0]
    for j in range(0, i):
        if end[j] <= i:
            tmp.append(table[j])
    table[i] = max(tmp) + price[i]

여기서 중요한 것은 3가지입니다.

---

1. 어떤 원소든 종료일자가 퇴사일자 이상이면 고려하지 않습니다.

2. 바텀업 방식을 쓰되, 테이블 초기화를 하지 않습니다. 첫번째 원소도 1의 예외조건에 걸릴 수 있기 때문입니다.

3. max함수는 빈 리스트에 대해 작동하지 않기 때문에, tmp변수에 미리 0을 넣어서 초기화해줍니다.

---

저같은 경우는 반복문 바깥에서 테이블을 쓸데없이 초기화해버려서, 2번의 문제가 있었습니다.