퇴사1 [SW역량] 14501. 퇴사 N수가 작아서, 완전탐색으로 풀어도되고, 그렇지 않고 가능하다면 DP로 풀어도 되는 문제이다. 여러가지 DP 해법을 보다가, 가장 와 닿는 풀이방법을 찾았다. d[i] : i일로부터 N일까지 최대 수익 이라고 정하면, 식을 자연스럽게 세울 수 있다. d[i] = max(d[i+1], d[i + t[i]] + p[i]) 이제 d[i]를 solve(int i)라고 놓고, 리턴값을 d[i]으로 설정해서 풀어보자. 그렇다 Top-down 방식의 동적계획법이다. 기저 조건은, d[N + 1] = 0 d[N + 1 초과] = - INF 라는 것이다. 이것은 예제 하나를잡아 하나하나 대입해가면서, 마지막 조건을 생각하면 이해가 쉬운 편이다. Hint: 마지막 날의 t[i]가 1이라면, d[i + t[i]] + p[i.. 2019. 10. 19. 728x90 이전 1 다음
