22115번 - 창영이와 커피
내림차순으로 정렬 후 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을 채울 수 있음
한 커피를 한 번만 마시는 게 보장이 되나요?
그런데 이렇게 하면 고쳐도 시간 초과 나요 ( 시간 복잡도 N ! )
KnapSack 알고리즘을 알아야 해요
newArr.remove(i);
를 통해 마신 커피는 제거하고있습니다!
시간 초과가 나오더라도 제가 어디서 틀렸는지 알고싶어요 ㅜㅜ
58번째 줄에 can 함수가 끝나고나면 newArr 에 i 번째 커피를 다시 넣어줘야 되지 않을까요?
newArr은 지역변수라 호출이 끝나면 사라집니다!
반례
5 2015 3 2 14 6
댓글을 작성하려면 로그인해야 합니다.
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을 채울 수 있음