[백준 2579번/c++] 계단 오르기

알고리즘

 

• 다이나믹 프로그래밍

 

---

풀이

계단 별 점수를 저장하는 벡터 s와 계단 점수의 최대값을 저장하는 벡터 dy를 사용하였다.

s[i] = i층 계단의 점수, dy[i] = i층 계단까지의 최대값

dy[1]=s[1]
dy[2]=s[1]+s[2]
dy[3]=s[3]+(s[1]과 s[2] 중 큰 값)
dy[i]=s[i]+(dy[i-2]와 dy[i-3]+s[i-1] 중 큰 값) (n>3)

 

•  s[i]+dy[i-2]
  • (i 계단의 점수) + (i - 2 계단까지 가는 최대값)
• s[i]+dy[i-3]+s[i-1]
  • (i 계단의 점수) + (i - 3계단까지 가는 최대값) + (i - 1 계단의 점수)

 

---

성공 코드

#include <bits/stdc++.h>
using namespace std;

int main() {
	// freopen("input.txt", "rt", stdin);
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	
	int n;
	cin >> n;
	vector<int> s(n+1, 0), dy(n+1, 0);
	for(int i=1; i<=n; i++){
		cin >> s[i];
	}
	dy[1]=s[1];
	dy[2]=s[1]+s[2];
	dy[3]=s[3]+max(s[1], s[2]);
	for(int i=4; i<=n; i++){
		dy[i]=s[i]+max(dy[i-2], dy[i-3]+s[i-1]);
	}
	cout << dy[n];
	
	return 0;
}