통증 (2)

문제

풀이

dp어려워잉

이전에 비슷한 문제는 그리디로 쉽게 해결할 수 있었지만, 이번에는 나머지가 생길 수 있기 때문에 그걸 어떻게 파악할지 유의하면서 풀었다.

dp 대표 유형이라서 금방 풀긴 했는데...응용문제가 나오면 어떻게 풀어야할지 모르겠다. 엉엉순대

dp 어려운것도 맞는데 dp가 진짜 무서운 점은 어떻게 공부해야 할 지 모르겠다는 거...

이번 풀이는 dp배열 생성 후 0부터 통증을 없애고자 하는 n값까지 반복하며 현재 횟수와 a,b를 뺀 뒤에 +1 한 값을 비교해서 더 작은값을 구하는 식으로 풀었다. 그래서 dp[0]을 제외한 나머지 배열에는 9999999로 대충 큰 값을 넣었다. a와 b에 자연수만 올 수 있고 n이 1000000이므로 널널한 값이다.

#include <iostream>
using namespace std;

int main(){
	int n,a,b,dp[1000001];
	
	cin>>n>>a>>b;
	for(int i=0;i<1000001;i++)
		dp[i]=9999999;
	dp[0]=0;
	for(int i=0;i<=n;i++){
		if (i-a>=0)
			dp[i]=min(dp[i],dp[i-a]+1);
		if (i-b>=0)
			dp[i]=min(dp[i],dp[i-b]+1);
	}
	if(dp[n]!=9999999)
		cout<<dp[n];
	else
		cout<<-1;
	return 0;
}