DP 는 아직도 너무 어렵다.

서울에서 경산까지 

https://programmers.co.kr/learn/courses/30/lessons/42899

프로그래머스

 

dp 테이블을 무엇을 기준으로 만들어야 하는지, 인덱스는 어떻게 잡는지가 어렵다.

처음에 나는 walk table, bike table만 만들었다. 즉 들른 도시의 수를 인덱스로 잡으려고 한 것이다.

도시를 인덱스로 잡은 후, 각 인덱스에 (남은 시간, 총 모금액)을 기록하려 했는데 너무 복잡했다.

 

쉬운 방법은 모든 것을 잘게 쪼개는 것이다! 도시 별로 (맞았다) 시간(K)을 인덱스(띠용!)로 삼은 배열을 만든다.

그리고 시간 별 모금액을 기록한다. 그러면 모든 경우에 대하여 모금액을 구할 수 있다!!

 

K보다 작은 시간 모금액 중 가장 큰 금액을 반환하면 된다.

 

DP는 정말 컴퓨터가 모든 걸 메모하게 하나보다...

 

코드 [링크]