백준 28071 승형이의 사탕 사기

DP를 이용해서 해결한 문제지만 효율적으로 푼 것 같지는 않다.

📜 문제 바로 가기 : 백준 승형이의 사탕사기

제출코드

import sys
input = sys.stdin.readline

N, M, K = map(int, input().split()) # 총 상자 개수, 가져갈 상자 개수, 동생 수
candy_box = list(map(int, input().split()))
candy_box.sort(reverse=True)
# 사탕수 별로 가져갈 상자 개수
candys = [0] * (M * candy_box[0] + 1) # 0개 ~ (고를 수 있는 상자 수 x 최대 캔디 개수)

for i in range(1, len(candys)):
    for cnt in candy_box: # 캔디 개수가 많은 것부터 꺼냄
        if cnt == i: # 딱맞는 경우
            candys[i] = 1
            break
        if cnt < i and candys[i-cnt]: # 캔디 수가 상자에서 꺼낸 캔디보다 많은 경우
            if candys[i-cnt] < M: # i - cnt  개를 만들 수 있는 상자수가 M개 보다 작은 경우엔 가능
                candys[i] = candys[i-cnt] + 1
                break # cnt 개수는 가장 줄어들기때문에 이걸 만족할때가 최소값이다.

ans = 0
for i in range(0, len(candys), K):
    if candys[i]:
        ans = i
    
print(ans)

---

접근방법

사탕을 0개부터 최대 개수까지 각 지점에서 나올 수 있는 경우의 수의 최소값을 DP 형식으로 구했다.