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;
}