[Gold V] 창영이와 커피 - 22115

문제 링크

성능 요약

메모리: 213080 KB, 시간: 884 ms

분류

다이나믹 프로그래밍, 배낭 문제

문제 설명

창영이는 커피를 좋아한다. 회사에 도착한 창영이는 아침 커피를 즐기려고 한다.

회사에는 N개의 커피가 각각 하나씩 준비되어 있고, 각 커피에는 카페인 함유량 Ci가 있다.

창영이는 N개의 커피 중 몇 개를 골라 정확히 K만큼의 카페인을 섭취하려고 한다.

창영이가 정확히 K만큼의 카페인을 섭취하기 위해서는 최소 몇 개의 커피를 마셔야 할까?

입력

첫째 줄에 커피의 개수 N, 창영이가 섭취해야 하는 카페인의 양 K가 주어진다.

둘째 줄에 N개 커피의 카페인 함유량 Ci가 주어진다.

출력

창영이가 K만큼의 카페인을 섭취하기 위해 마셔야 하는 커피의 최소 개수를 출력한다.

만약 정확히 K만큼의 카페인을 마실 수 없으면 -1을 출력한다.

---

풀이

아이디어

"탑다운"으로 풀고 싶다 라는 생각이 들었고, 배낭문제를 연습하려 했지만, 뭔가 일반적인 배낭문제와는 조금 다른 응용이라고 생각되었다. 지금 생각해보니 문제를 뒤틀어 생각하면 그냥 배낭문제처럼 풀 수 있었을듯.

최적화 문제의 기본 생각 구현 틀을 유지하려고 노력했던 문제

1. 완전탐색으로 먼저 문제를 설계한다.
2. 반환값은 전체가 아닌 부분문제의 답만 반환하도록 정의를 바꿈
3. 입력이 배열이거나 문자열인 경우 가능하다면 적절한 변환을 통해 메모이제이션
4. 최적 부분구조 확인

이를 통해 구현한 함수 모형은 다음과 같다.

• f(k, idx) : k는 먹어야 하는 남은 카페인, idx는 앞으로 방문해야할 커피중 가장 작은 인덱스

기저사례는 다음과 같이 정의하였다

• k가 0인 경우 (먹어야 할 카페인을 다 먹은 경우)
• idx가 끝에 도달한경우

또한 해당 인덱스의 커피를 선택한 경우 나중에 1을 더해주고, 그렇지 않은경우 그대로 반환한다.
그 중에서 작은 값을 부분문제의 정답으로 한다.

또한 문제에서 전처리 해주어야할 부분은 먹어야 할 카페인의 양이 0인경우로, 이때는 별다른 처리없이 0을 출력하고 프로그램을 종료한다.

코드

INF = 1001
n, m = map(int, input().split())
if m == 0:
    print(0)
    exit()

caffain = list(map(int, input().split()))
dp = [[-1]*(101) for _ in range(100001)]

def solve(k, idx):
    if k- caffain[idx] == 0:
        return 1
    
    if idx == n-1:
        return INF
    
    if dp[k][idx] != -1:
        return dp[k][idx]
    
    dp[k][idx] = min(solve(k-caffain[idx], idx+1) + 1, solve(k, idx+1))
    return dp[k][idx]

result = solve(m, 0)
print(result if result != INF else -1)

---

회고

배낭문제를 이해하기 위해 많이 노력했던 문제.
나름 이제 매커니즘을 이해한 것 같다.