문제 -
하루에 최대 8시간 일할 수 있을 때
주 52시간을 채울 수 있는 경우를 배열 형태로 모두 출력하라
ex) [4,8,8,8,8,8,8], [5,7,8,8,8,8,8] ...
이렇게 완전탐색을 돌면서 일한 시간을 choice배열에 기록한다음
기저사례 들 때마다 list에 add 하는 식으로 짯음.
답은 330개랑 배열도 잘 출력됨.
이건 메모이제이션을 적용한 모습인데...
답은 330 당연히 잘 나옴.
근데 그 경우들을 못 구하겠당... 어떻게 구할 수 있을까...
완탐
경우 구하려면 완탐이 제일 편하지
메모이제이션은 보통은 경우의 수만 빠르게 구하고 싶을때 사용한다고 생각하셈
물론 하려면 못하는건 아닌데 완탐보다 못함
형아 종만북 보면 그래도 메모이제이션하고 그 메모에 저장된 정보를 바탕으로 경우를 구하던데... 이거는 적용 못할까?
일단 답의 목록을 다 구해서 출력해야 하니까 메모이제이션을 해도 완탐보다 빨라지기 어렵다는걸 생각해야함
그리고 정보를 바탕으로 경우를 구할수는 있는데 정보에서 목록을 출력하는게 완탐을 다시 돌리는거랑 비슷함
오호 ㄱㅅㄱㅅ
LIS같은 거 말하는 거면, 그런 것들은 문제 자체가 DP로 경우를 구할 수 있게 되어있고, 그 경우도 하나라서 되는 거일걸
뭐 어떻게든 잘 하면 가능은 할텐데 왠만하면 그냥 완탐 쓰는 게 나은 경우가 많을 듯.. 그리고 달팽이 문제 O(1)에는 푸는 게 불가능하듯이, 시간 복잡도는 답의 개수 이하로는 못 줄어듦
달팽이?
달팽이?