[Python] 백준 #15486- 퇴사 2 [try_again]

문제

---

15486번: 퇴사 2

코드

---

My answer

import sys
input=sys.stdin.readline

n=int(input())
tmp,price=[],[]

for i in range(n):
    tmp.append(list(map(int,input().split())))
tmp.append([0,0])

price=[i[1] for i in tmp]

for i in range(n-1,-1,-1):
    if(i+tmp[i][0]>n):
        price[i]=0
        continue
    prev=i+tmp[i][0]
    if(prev!=n):
        price[i]=price[i]+max(price[prev:]) 
#print(price)
print(max(price))
------------------------------------------------------------------
import sys
input=sys.stdin.readline

n=int(input())
tmp,price,mtmp=[],[],0

for i in range(n):
    tmp.append(list(map(int,input().split())))
tmp.append([0,0])

price=[i[1] for i in tmp]

for i in range(n-1,-1,-1):
    if(i+tmp[i][0]>n):
        price[i]=0
        continue
    prev=i+tmp[i][0]
    mtmp=max(mtmp,price[prev]+price[i])
    if(prev!=n):
        price[i]=mtmp
print(max(price))

My answer

import sys
input=sys.stdin.readline

n=int(input())
tmp,price=[],[]

for i in range(n):
    tmp.append(list(map(int,input().split())))
tmp.append([0,0])

price=[i[1] for i in tmp]

for i in range(n-1,-1,-1):
    if(i+tmp[i][0]>n):
        price[i]=price[i+1]
        continue
    prev=i+tmp[i][0]
    price[i]=max(price[i]+price[prev],price[i+1])
    
#print(price)
print(max(price))

Another answer

import sys 
input = sys.stdin.readline 

n = int(input())
t,p = [],[]
dp = [0] * (n+1)
for i in range(n):
    x,y = map(int,input().split())
    t.append(x)
    p.append(y)
M = 0 
for i in range(n):
    M = max(M,dp[i])  
    if i+t[i] > n :  
        continue 
    dp[i+t[i]] = max(M+p[i],dp[i+t[i]])
print(max(dp))

 

풀이

---

우선 내 코드는 두가지 다 안돌아간다. 첫번째 코드는 이론상 맞는 것 같은데 시간초과가 뜬다. for문안에 있는 max와 슬라이싱 때문에 그런 것 같아서 두번째 코드를 작성한건데 이건 긴가민가 했다. 그래도 예시 4개가 모두 돌아가서 제출해봤더니 시간초과는 안뜨지만 틀렸다. 그래서 지금 첫번째 코드 이론자체가 틀린건지 아니면 시간초과를 해결하는 과정에서 이상해진건지 정확히 모르겠다.. 다른 분들의 코드를 찾아보니 전부 나와 다르게 풀어서 내 방법으로 꼭 풀어보고 싶었는데 못풀었다.. 우선 이 문제는 dp문제다. 다른 코드와 큰 틀은 비슷하지만 난 맨 뒤에서부터 시작해서 계산을 했고 다른 코드는 모두 앞에서부터 차례대로 했다. 아래 코드의 자세한 풀이는 https://dndi117.tistory.com/entry/aaa 여길 참조하길 바란다.... 제 코드의 문제점을 알려주실 분을 찾습니다..........너무나도 저 방법으로 풀고 싶습니다. 혼자 끙끙앓다가 알아낸 방법이어서..

문제를 해결했다. 첫번째 코드는 역시 틀린게 아니라 for문 안에 있던 슬라이싱과 max의 반복적 사용때문인 것 같다. 우연히 뒤적거리다가 다른 분의 코드를 보고 비슷해서 내꺼에서 조금만 바꿔봤는데 시간이 오래걸리긴하나 돌아갔다. 수정한부분은 max부분이었는데 나도 저 방법을 했었는데 왜 안돌아간건지 모르겠다...아무튼 뒤에서 누적시키는 것도 틀리지 않았다는 걸 밝혀냈다. 내 최종수정코드는 첫번쨰 코드에다가 https://whatryando.tistory.com/m/75 이분의 블로그에서 코드를 보고 조건식하나를 참조했다. 

백준 15486 퇴사 2 풀이/코드 (파이썬) 다이나믹 프로그래밍