2020. 11. 10. 22:36ㆍcoding study
[동적 계획법]
이때 동적 계획법이란,
일반적으로 주어진 문제를 풀기 위해서, 문제를 여러 개의 하위 문제(subproblem)로 나누어 푼 다음, 그것을 결합하여 최종적인 목적에 도달하는 것이다. 각 하위 문제의 해결을 계산한 뒤, 그 해결책을 저장하여 후에 같은 하위 문제가 나왔을 경우 그것을 간단하게 해결할 수 있다. 이러한 방법으로 동적 계획법은 계산 횟수를 줄일 수 있다. 특히 이 방법은 하위 문제의 수가 기하급수적으로 증가할 때 유용하다.
사진 출처 : www.acmicpc.net/problem/2579
[조건]
중요하게 봐야하는 조건은 연속된 세개의 계단을 연속으로 밟지 않아야 한다는 것, 시작점은 계단에 포함되지 않는다는 것이다.
즉, 계단을 오를 때는 1칸 또는 2칸까지 연속으로 가능하다. 또한 마지막 계단은 밟아야 한다는 것이다.
거꾸로 생각해봤을 때 마지막 계단을 무조건 올라야 하므로 마지막 계단을 기준으로 2가지의 방식으로 나눠볼 수 있다.
1) 마지막 칸 기준으로 2단계 전 칸을 밟아야 한다.
n-2+n
2) 마지막 칸 기준으로 한 단계 전 칸을 밟으면서 연속3칸은 불가능하므로 3단계 전 칸도 밟아야 한다.
n-3+n-1+n
[풀이]
|
#include <iostream> using namespace std;
int max(int a, int b) { if(a>b) return a; else return b; }
int main(){
int num; int stair[301]; //최대 개수 300이므로 301개 설정 int dp[301];
cin >> num;
for (int i = 0; i < num; i++) { cin >> stair[i]; }
for (int i = 0; i < 3 && i <= num; i++) if (i!=2) dp[i] = dp[i - 1] + stair[i]; else dp[i] = max(stair[i] + dp[i - 2], stair[i] + stair[i - 1]);
for (int i = 3; i < num; i++) dp[i]=max(stair[i] + dp[i - 2], stair[i] + stair[i - 1] + dp[i - 3]);
cout << dp[n - 1] << '\n';
return 0;
}
|