백준 16568 엔비스카의 영혼

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

문제와 채점은 위 사이트에서 확인 하실 수 있습니다

 

이 문제는 한길이가 앞에 있는 N명의 사람들의 앞으로 가는 가장 빠른 시간을 구하는 문제입니다. 한길이는 3가지의 동작을 취할 수 있으므로

어떤 i번째 사람의 앞까지 도달하는데 걸리는 시간을 저3가지의 동작중 가장 적게 걸리는 시간이 답이됩니다. 따라서 dp를 이용하여 N번까지 가는데 시간을 구해주면 됩니다.

 

다음은 코드입니다.

 

#include <iostream>

using namespace std;

int main(void) {
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	int dp[1000001];
	int N,a,b;
	cin >> N >> a >> b;	
	fill_n(dp, 1000001, 1000001);
	dp[0] = 0;
	
	for(int i = 1; i <= N; i++) {
		dp[i] = dp[i-1] + 1;
		if(i-a-1 >= 0)
			dp[i] = min(dp[i], dp[i-a-1] + 1);
		if(i-b-1 >= 0)
			dp[i] = min(dp[i], dp[i-b-1] + 1);
	}
	cout<<dp[N];
	return 0;
}