S3 14501. 퇴사

문제 보기 :  14501번: 퇴사

---

문제

• 정답률 : 50%

---

작성 코드 & 풀이 과정 코멘트

# import sys
# input = sys.stdin.readline

n = int(input())
t = [0] ; p = [0]
for _ in range(n):
    t1, p1 = map(int,input().split())
    t.append(t1) ; p.append(p1)

cost = set()
cost.add((1+t[1],p[1]))
maxx = 0

for i in range(2,n+1):
    possible = []
    for dd,pp in cost: #4,10
        if i >= dd and i+t[i] <= n+1: #2 >= 4
            possible.append((dd+t[i],pp+p[i]))
    
    if possible:
        possible.sort(key=lambda x:(-x[1],x[0]))
        cost.add(possible[0])
        maxx = max(maxx, possible[0][1])
    elif i+t[i]<=n+1 and not possible:
        cost.add((i+t[i],p[i]))
        maxx = max(maxx, p[i])
    
print(maxx)

처음에는 이렇게 풀이했고, 예제 케이스는 패스했다. 
근데 제출했을 때 에러가 나서 다시.. 갈아 엎었다..

(왜 난 이걸 dp로 생각했을까 ㅠ)

import sys
input = sys.stdin.readline

n = int(input())
t = [0]*(n+1) ; p = [0]*(n+1)
for i in range(1,n+1):
    t[i], p[i] = map(int,input().split())

cost = [0]*(n+2)

for i in range(1,n+1):
    cost[i+1] = max(cost[i+1],cost[i]) #+p[i])

    if i+t[i]<=n+1:
        cost[i+t[i]] = max(cost[i+t[i]],cost[i]+p[i])

print(cost[-1])

그날 상담을 했을때와 안했을 때로 경우를 나눠서 입력해서 업데이트하는 방식으로 변경했고, 이건 패스했다!