1105. Filling Bookcase Shelves

1105. Filling Bookcase Shelves

https://leetcode.com/problems/filling-bookcase-shelves/

문제

풀이

1. i = 0일 때 height = 1
2. i = 1일 때 첫 번째 경우의 수(1shelf = 1, 2shelf = 3) => 4, 또는 두 번째 경우의 수(1shelf = 1, 1shelf = 3) => 3이 될 수 있다. 여기서 최소값은 두 번째 경우의 수(1shelf = 1, 1shelf = 3) => 3이 된다.
3. i = 2일 때 첫 번째 경우의 수(1shelf => 3, 2shelf => 3) => 6, 또는 두 번째 경우의 수(2와 3이 2shelf일 때 1shelf = 1, 2shelf => 3) => 4, 하지만 세 번째 경우의 수(1, 2, 3)이 하나의 shelf에 있을 수는 없다. 그 이유는 shelf_width를 넘어가기 때문이다.
4. i = 3일 때 첫 번째 경우의 수(기존에 shelf에서 새로운 shelf을 만들 때 1shelf => 1, 2shelf => 3, 3shelf => 1) => 5, 또는 3,4가 shelf일 때를 생각해보자 (1shelf => 3, 2shelf => 3) => 6이 될 것이다. 하지만 2,3,4가 shelf일 때를 생각해보면 shelfwidth를 넘어가기 때문에 되지 않는다.
   이와 같은 로직으로 DP표를 만들면 다음과 같다.
   
   shelf_width를 넘어가지 않는 범위에서 그 전에 값을 비교해서 max값을 찾는다.

결과