[백준14501] 퇴사

문제

---

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

14501번: 퇴사

 

생각의 흐름

---

무려 삼성SW역량테스트 기출문제이시다....

DP를 이용하는 문제라는 건 감을 잡았는데 알고리즘을 어떻게 적용해야 할지 떠오르지 않아 다른 분의 코드를 참고하고 이해하였다.(출처는 코드 밑단에 추가해두었다)

1. 비용을 계산해야 하니 비용을 담을 dp list를 만든다.
2. 그 다음 애초에 불가능한 상담들(퇴사 일자 이후까지 상담이 진행되어야 하는 경우)을 분별해내야 하는데 이는 소요일수를 담은 t list의 값을 참조해 해당 일수 만큼 상담을 진행했을 시 퇴사하는 날을 넘어버리는지를 검사한다.
3. dp에 마지막으로 0을 append하고 뒤에서부터 갱신하는 방식으로 dp를 적용한다.
4. 여기서 핵심은 dp를 적용시켜 리스트 값을 갱신할 때 앞이 아닌 뒤에서부터 앞으로 진행한다는 것이다. 이유는 두 가지로 볼 수 있는데

   • 뒤에서부터 소요 시간을 따져봐야 2번에서 언급한 상담들을 걸러내어 시작점을 잡을 수 있기 때문이다.

   • 걸리는 시간을 고려할 때 뒤에서 앞으로 계산을 해야 소요 시간에 구애받지 않는다.(시간은 앞에서 뒤로 흘러가니까)

 

깨달은 점

---

리스트를 역순으로 참조하고자 할 때는 세 번째 인자에 -1을 넣어주어 range(n-1,-1,-1)과 같이 쓸 수도 있다는 사실!!(이 때, 두 번째 인자의 -1은 참조 시 포함되지 않는다. 즉 [n-1,n-2,...,0]) 

 

코드

---

n = int(input())
t = []
p = []
dp = []

for i in range(n):
    a, b = map(int, input().split())
    t.append(a)
    p.append(b)
    dp.append(b)
dp.append(0)

for i in range(n-1,-1,-1):
    if i+t[i]>n:
        dp[i] = dp[i+1]
    else:
        dp[i] = max(dp[i+1], dp[i]+dp[i+t[i]])

print(dp[0])

### 출처:https://pacific-ocean.tistory.com/199