백준 2579번, 계단 오르기

백준 2579번 c++ 문제풀이

문제:

백준 2579

풀이:

1. 벡터 v에 입력값 저장.
2. 배열 sum[n]에 n층 까지의 최댓값 저장.
3. sum[1] = v[0].
4. sum[2] = v[1] + v[0].
5. sum[3] = v[2] + v[0] or v[1] + v[2] 둘중 최댓값.
6. sum[n]의 점화식 = sum[n] = max(sum[n-2]+v[n-1], sum[n-3] + v[n-1]+v[n-2]);
7. 규칙을 잘 파악하고 점화식을 잘 세우는게 dp를 풀 때의 핵심인 것 같다. 처음에 식을 잘못 세워 시간을 낭비했다.

코드:

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int sum[301]; 


int main(){

ios_base::sync_with_stdio(false);
cin.tie(nullptr);

vector<int> v; //입력 값 저장.

int s;

cin >> s;

for(int i=0;i<s;i++){
    int input;
    cin >> input;
    v.push_back(input);    
}
sum[1] = v[0]; 

sum[2] = v[0] + v[1]; 

sum[3] = max(v[0]+v[2], v[1] + v[2]);

for(int i=4;i<=s;i++){
    sum[i] = max(sum[i-2]+v[i-1], sum[i-3] + v[i-1]+v[i-2]);
}

cout << sum[s] <<"\n";

return 0;
}

감사합니다.