[2579] 계단 오르기, c++

[2579] 계단 오르기

 

www.acmicpc.net/problem/2579

2579번: 계단 오르기

한줄 후기 : 우리집 계단은 너무 높아

 

#include <iostream>
#include <algorithm>
using namespace std;
int main(){
	int arr[301];
	int dp[301];
	int n;
	cin >> n;
	for(int i=1; i<=n; i++){
		scanf("%d", &arr[i]);
		dp[i] = arr[i];
	}
	dp[2] = max(arr[1]+arr[2], arr[2]);
	dp[3] = max(arr[1]+arr[3], arr[2]+arr[3]);
	for(int i=4; i<=n; i++){
		dp[i] = max((dp[i-3]+arr[i]+arr[i-1]), (dp[i-2]+arr[i]));
	}
	cout << dp[n];
	return 0;
}

이것도 예전에 한번 풀다가 실패한 문제

알고스 과제 내야해서 다시 풀어봄

​

dp[n] => n번째 계단에서 최고 점수

경우는 두 가지

연속 세칸을 오를 수 없으니 한칸 전을 밟았다는 소리는 그 전전 칸 즉 i-3째 칸을 밟았다는 소리다.

그러므로 dp[i] = dp[i-3]+arr[i-1]+arr[i]

다른 한 가지는 전전 칸을 밟고 바로 올라온 경우

dp[i] = dp[i-2]+arr[i]

두 경우에서 max 값을 뽑아 주면 된다.

dp 초기 값 정하기가 까다로웠음