문제
Input:
books = [[1,1],[2,3],[2,3],[1,1],[1,1],[1,1],[1,2]]
shelfWidth = 4
books = [[1,3],[2,4],[3,2]]
shelfWidth = 6
Output:
6
4
요약:
책들의 넓이와 높이를 담은 books[i] = [thicknessi, heighti] 라는 배열이 주어지고 선반의 넓이가 주어진다
책을 선반위에 놓을때 주어진 책의 순서대로 놓아야하며 선반의 넓이를 넘어서게되면 새로운 선반에 책을 놓을 수 있다
선반을 계속 두면서 책을 쌓아 올리는데 여기서 책을 쌓을 수 있는 최소한의 높이를 구하라
조건:
1 <= books.length <= 1000
1 <= thickness <= shelfWidth <= 1000
1 <= height <= 1000
풀이 과정
이해:
이 문제는 결국 모든 가능성을 한번씩 다 봐야 한다
책이 순서대로 선반 위에 올라간다는 조건을 만족해야 하기 때문에 그렇게 많은 가능성이 생기지 않아 재귀적으로 어느정도 처리가 가능하나 그럼에도 불구하고 시간복잡도는 꽤 높다
문제 나누기:
문제를 작게 나누어서 바라보면 각 책을 올릴 때마다 두 가지 선택이 있다
- 현재 선반에 책을 올리기
- 새로운 선반에 책을 올리기
하지만 이를 모든 책에 대해 반복하면 시간복잡도는 기하급수적으로 증가한다
결론:
재귀적으로 모든 경우를 계산하면서 각 상태를 저장하게되면 재귀가 풀리면서 어떤 선반에 놓을지 결정할 때에 이전의 결과값이 남아 있으므로 몇번 뒤로가지 않고도 곧바로 이어서 재귀를 들어가 해당 경우에 대한 뒤의 해를 풀 수 있기에 Dynamic Programming(DP)를 이용해 풀면 되겠다는 생각이 들었다
풀이:
못풀었따 DP에 저장할 값의 기준을 못정하겠다
DP문제를 많이 풀어본적이 없어 감이 잘 오지 않는다...
P.S.
class Solution {
public:
int minHeightShelves(vector<vector<int>>& books, int shelfWidth) {
int n = books.size();
int f[n + 1];
// 선반의 최소 높이
// f[i]는 i개의 책이 선반에 올라왔을때의 최소 높이
f[0] = 0;
for (int i = 1; i <= n; ++i) {
//w: 넓이, h: 높이
int w = books[i - 1][0], h = books[i - 1][1];
// 새로운 선반에 책을 올려놓을때의 높이
f[i] = f[i - 1] + h;
// 이전 선반으로부터 최소 높이를 구함
for (int j = i - 1; j > 0; --j) {
// 이 책을 현재 선반에 넣었을 때
// 이전에 올려놨던 책들을 전부 현재 선반에 올려놓는 경우
w += books[j - 1][0];
if (w > shelfWidth) {
break;
}
// 현재 선반에 위치한 책들중 가장 높은 책 높이 구하기
h = max(h, books[j - 1][1]);
// 이들중 최소 높이 갱신
f[i] = min(f[i], f[j - 1] + h);
}
}
return f[n];
}
};
엄청 간단해보이는 풀이방법을 가져왔다
재귀 대신 반복문으로 각 선반에 책이 올라오는 모든 가능성을 확인하는 방식이다
반복문이 내부와 외부로 갈라지는데
외부에서 f[i]는 새로운 선반에 책을 올려 놓았을 경우의 높이를 구하는 것이고
내부에서 f[i]는 현재 선반에 이전의 책들을 같이 올려놓았을때를 구해
외부와 내부에서 찾은 이 두 높이를 비교하여 f[i]에 최소의 높이를 구하는 것이다
이 코드 이해하는데 너무 오래걸렸다...
그림까지 그려가며 고민을 했었는데 내가 너무 애초에 복잡하게 생각해서 단순한 코드에 복잡하게 다가갔던것 같다