아 시발 DP 증명 못하나

[새콤(secom0)]

블로그 같은데 돌아보면

저 이렇게 풀었어요 하는데

그게 왜 성립하는지 도저히 이해가 안감

아 진짜 너무 답답하다

[17번(wjd918273)]

뭔문제길래 - dc Cpp

[17번(wjd918273)]

https://www.acmicpc.net/problem/2839
이런거 예시로 들면 - dc Cpp

[익명(222.238)]

탐욕알고리즘으로 할수 있지않나?

[17번(wjd918273)]

5kg 최소 봉지개수 1개인건 자명하고, 6kg면 2개인게 자명할거임. 그럼 여기서 8kg는 5kg에 봉지 단 하나만 추가하면 최소 개수겠지. 이런식으로 접근하는거지 뭐 - dc Cpp

[17번(wjd918273)]

9kg짜리면 5kg부터 대뜸 넣을경우 4kg남고 3담으면 1남으니 -1출력할거임? - dc Cpp

[17번(wjd918273)]

3kg 3봉지로 가능함. - dc Cpp

[17번(wjd918273)]

결국 무슨값을 어떻게 저장할지 그런게 중요하지. 5kg에 쓰이는 봉지 수가 1개. 그러면 arr[5] = 1 이런식으로 저장해둘 수 있겠지. 인덱스 0부터 시작하는게 더 편하면 [4]로 하든지 - dc Cpp

[17번(wjd918273)]

[5 + 3], [5 + 5]에다가는 각각 arr[5] + 1 넣고. 그런식으로 원하는 kg수까지 인덱스 접근해나가면 됨 - dc Cpp

[17번(wjd918273)]

dp 머리 좀 더 박고 공부하면 될거임 - dc Cpp

[익명(106.248)]

DP는 공간 복잡도를 조금 더 써서 시간복잡도를 낮추는거라 알고리즘 풀이 자체는 더 간단한 풀이로도 됨