백준 Gold 5 창영이와 커피

창영이와 커피 (백준 Gold 5)

https://www.acmicpc.net/problem/22115

n개의 커피와 필요한 카페인 양 k가 주어질 때
k를 얻기 위한 최소 커피 섭취 횟수를 구하는 문제

• 불가능 하다면 -1 출력

풀이 방법

dp 정의

• dp[i] : i값으로 만들기 위해 마셔야 하는 최소 커피 수
  

• 도달 불가능 확인을 위해 -1로 초기화
  

• 다만 dp[0] = 0;
  (카페인을 안마시는 경우 필요한 커피 횟수는 0이므로 정의에 부합)
  

다음 상태 이동(점화식)

• 먼저 dp[j-caf[i]] 가 -1 인지 파악하기
  
  • -1 이라면 해당 주기는 Pass
    
  • 아니라면 현재 dp[j] 상태를 확인하기
    
    • dp[j] == -1 이라면 dp[j-caf[i]] + 1
      
    • 아니라면 dp[j] = min(dp[j], dp[j - caf[i]] + 1)
      

• 이전 단계가 가능한지를 -1 로 파악하기
  

• 커피를 ‘마시는 경우’ + 1 이므로 체크
  

순회 방식

• 1차원 dp이며, 같은 커피를 마실 수 없으므로 내림차순 진행
  

제출 코드

#include<iostream>
#include<vector>

using namespace std;

int main()
{
	int n, k;
	cin >> n >> k;

	vector<int> caf(n);
	for (int i = 0; i < n; i++)
	{
		cin >> caf[i];
	}

	vector<int> dp(k + 1, -1);
	dp[0] = 0;

	for (int i = 0; i < n; i++)
	{
		for (int j = k; j >= caf[i]; j--)
		{
			if (dp[j - caf[i]] == -1)
				continue;

			if (dp[j] == -1)
				dp[j] = dp[j - caf[i]] + 1;
			else
				dp[j] = min(dp[j], dp[j - caf[i]] + 1);
		}
	}

	cout << dp[k];

	return 0;
}

결과

패턴화가 어느정도 되어
비교적 쉬운 문제는 빠르게 풀 수 있었다