15678번: 연세워터파크
15678번: 연세워터파크 - DP kks227님 블로그의 동적계획법 4를 읽고 인상 깊어 작성하게 되었다.이 문제는 임의의 시작점에서 번호가 증가하는 방향으로 징검다리를 건너게 되는데한번에 D개 이하의 징검다리를 뛰어넘을 수 있을 때 점수의 최댓값을 구하는 문제이다.풀이는 간단하다.어떤 도착점 k의 관하여 dp(k)를 도착점 k에 도착했을 때 얻을 수 있는 최대 점수라 하면,dp(k)는 max(0, k-D) ~ k까지의 dp값 중 최댓값이 된다.이후 모든 i에 대하여 dp(i)의 최댓값이 답이다. 이 때 구간에 대하여 최댓값을 구하는 과정을 반복하여야 한다.구간이기에 구간 트리를 이용하여 O(lgN)만에 최댓값을 찾을 수 있고이는 시간복잡도가 O(NlgN)만에 문제를 해결할 수 있다. 이 때 kks22..
문제 해결/백준 온라인 저지
2019. 1. 3. 03:05