[ BOJ / 파이썬 ] 14501.퇴사

공부의 참맛을 느껴가는 중... 아 기분 좋다 진짜 ..🤸‍♀️

 

해당 문제는 현재 한국 코테 바이블 이코테에 수록되어 있는 문제인데 대학 다니면서 처음 코딩테스트에 대해 접한 초반에 풀어보고 진짜 이해가 도통 되지 않아 좌절했던 문제다.

 

 

풀이가 이해된 뒤에도 뒤에서부터 인덱스를 접근해야만 이 문제를 풀 수 있나..? 싶어서 계속 의아했었는데

드디어 내 사고방식에 근거해서 이 문제를 풀 수 있었다.

 

 

n = int(input())
T = []
P = []
total = [0] * (n+1)
for i in range(n):
  time, price = map(int, input().split())
  T.append(time)
  P.append(price)

for i in range(n):
  if i > 0:
    total[i] = max(total[i-1], total[i])
  if i+T[i] <= n and total[i+T[i]] < total[i] + P[i]:
    total[i+T[i]] = total[i] + P[i]
print(max(total))

 

 

정말 놓치지 말아야하는 포인트는 예제 1,2에서는 퐁당퐁당으로 결과가 쭉 이어지지만,

예제 3, 4 같은 경우는 해당 시점의 dp테이블보다 그 전의 dp테이블값이 큰 경우를 고려해야한다는 것이다.

 

 

그러니까 내가 서있는(검사하는) 그 시점의 dp테이블을 시작값이라고 볼 때(이미 전부터 갱신되어온), 그 과거 dp테이블 중 최신값인 내 바로 이전 값(검사 시작 전)을 검사해주며 더 큰 값을 초기값으로 봐야한다는 것이다.

그걸 i-1 과 i 의 관계식만으로 비교 가능한가 ? 스스로 의심했는데. 사실 for문을 순서대로 돌며 차례차례 업뎃해왔으므로 바로 전 값을 가장 max값이라고 여기고 바로 접근하는게 이상하지 않다.

 

 

 

개인적으로 너무 까다로운 문제다.. 내 이해방식에 잘 들어맞지 않아 고생이다.. 

이게 제일 중요한건데! 급여 문제잖아 이건..;; 

해당 유형 관련해서 회의실 예약, 뭐 예약 등등 자주 쓰이는 알고리즘이니까 확실히 익혀둘 필요가 있다.

 

이거 응용 문제도 있는데 걔도 풀어봐야 확실히 구조가 잡힐 것 같다.