youhogeon   2년 전

내림차순으로 정렬 후 K보다 큰 커피는 제거하고

남은 커피들에 대해 반복 하면서 반복문 안에서

재귀를 이용해 푸는 알고리즘입니다.

ex : K가 8이고 커피가 [2 3 5 7 9] 인 경우

1. K보다 작은 원소는 모두 제거함 [7 5 3 2]

2. 가장 큰 원소를 쓴다고 가정하고 K가 1(= 8 - 7)이고 커피가 [5 3 2]라고 하고 재귀

3. K가 1이므로 커피 모두 제거 -> 불가능

4. 7커피 는 사용 불가이므로 5커피 사용한다고 가정. K는 3(=8-5)이고 커피는 [7 5 3 2]

5. K가 3이므로 7커피 5커피 제거

6. K가 3이므로 3커피 이용해 한잔 마실 수 있음

7. 3커피 5커피 이용해 총 두잔으로 카페인 8을 채울 수 있음

dtc03012   2년 전

한 커피를 한 번만 마시는 게 보장이 되나요?

그런데 이렇게 하면 고쳐도 시간 초과 나요 ( 시간 복잡도 N ! )

KnapSack 알고리즘을 알아야 해요

youhogeon   2년 전

newArr.remove(i);

를 통해 마신 커피는 제거하고있습니다!

youhogeon   2년 전

시간 초과가 나오더라도 제가 어디서 틀렸는지 알고싶어요 ㅜㅜ

dtc03012   2년 전

58번째 줄에 can 함수가 끝나고나면 newArr 에 i 번째 커피를 다시 넣어줘야 되지 않을까요?

youhogeon   2년 전

newArr은 지역변수라 호출이 끝나면 사라집니다!

youhogeon   2년 전

반례

5 20
15 3 2 14 6

댓글을 작성하려면 로그인해야 합니다.