#2579 계단 오르기

# 문제

# 입력 및 출력

# 풀이

처음에 생각했던 내용은 맨마지막 계단은 무조건 선택해야하니까 뒤에서부터 계단 선택 여부를 결정하는 방식으로 해결하려고 했는데 계단 선택 조건이 두개나 있어서 너무 복잡해지더라,,

그래서 결국 구글링ㅋㅋ,,,

 

dp배열과 계단 배열을 하나씩 만들어줌

1) 계단이 1개일땐 무조건 선택해야하므로 계단배열의 1인덱스값을 그대로 dp배열에 넣어주면 됨

2) 계단이 2개일땐 계단 두개를 모두 선택하는게 최대값이 됨 -> 이 값을 dp 배열에 넣어주기

3) 계단이 3개일땐 계단 1, 계단 3 / 계단 2, 계단 3 둘 중의 최대값을 dp배열에 넣어주면 됨

4) 계단이 3이상일땐 두가지 경우가 있음

   a) n-1 계단을 선택하는 경우

      n 계단 점수 + n-1 계단 점수 + n-3 계단까지의 점수 최대값

      (왜냐하면 n-2계단은 선택하지 못하기 때문 -> 연속 3개는 선택이 안되니까)

   b) n-1 계단을 선택하지 않는 경우

      n 계단 점수 + n-2 계단까지의 점수 최대값

https://yabmoons.tistory.com/20

[ 백준 2579 ] 계단오르기 (C++)

 

그림으로 나타내면 이런식임

#include <iostream>
#include <algorithm>
using namespace std;
int dp[301], stair[301];

int fun(int n) {
	if (n == 1) return stair[1];
	else if (n == 2) return stair[1] + stair[2];
	else if (n == 3) return max(stair[2] + stair[3], stair[1] + stair[3]);
	else return max(dp[n - 2] + stair[n], dp[n - 3] + stair[n - 1] + stair[n]);
}

int main() {
	int n;
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> stair[i];
	}
	for (int i = 1; i <= n; i++) {
		dp[i] = fun(i);
	}
	cout << dp[n];
}

처음 제출한게 틀린 이유는 n이 3일때 조건을 잘못 걸어줘서 틀렸음ㅋㅋ

 

dp 점화식 찾는게 너무 힘드넹,,

dp 문제는 진짜 많이 풀어서 감으로 찾는 수밖에 없을 것 같다,,