2579 - 계단 오르기

문제

2579번: 계단 오르기
문제가 길어 링크로 대체 했습니다.

코드

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

int n;
int a[304];
int dp[304];

void solve(){
	dp[1] = a[1];
	dp[2] = a[1] + a[2];
	dp[3] = max(a[1] + a[3], a[2] + a[3]);
	for(int i = 4; i <= n; i++){
		dp[i] = max(dp[i-2] + a[i] , dp[i-3] + a[i-1] + a[i]);
	}
	cout << dp[n] << '\n';
}

int main(){
	cin >> n;
	for(int i = 1; i <= n; i++){
		cin >> a[i];
	}
	solve();
}

풀이

경우의 수를 체크하는 경우, 이전 값과의 비교가 필요한 경우, 범위가 엄청나게 크지 않은 상황이었기에 DP가 떠올랐다.
a는 계단의 값을 의미하는 배열, dp는 해당 인덱스에서 최대값을 가지는 값을 의미하도록 생각했다.
점화식을 만들어 사용하기 위해 규칙을 찾아봤다.
계단이 3개가 연속으로 올 수 없다고 하니 3개를 기준으로 생각해봤다.
dp[1]은 무조건 a[1],
dp[2]는 무조건 a[2] (계단의 점수는 자연수이기 때문)
dp[3]은 a[1] + a[3], a[2] + a[3]의 값 중 더 큰 값을 가진다.
4번째부터는 조건을 규칙을 갖게 되는데
계단이 3연속으로 올 수 없기에 dp[4]는 세 칸 전까지의 최대 값 or 한 칸 전의 값 + 3칸 전까지의 최대 값 중 더 큰 값을 가지게 된다.

결과

후기

큰 범위를 쪼개거나? 모든 경우의 수를 체크해볼 때 주로 DP를 사용하는 듯한 느낌이 드는데 나만의 설계 방식으로 DP배열을 만드는게 아직도 감이 잘 안잡힌다...ㅜ
막상 보면 알겠는데 처음 풀어나가는 방법에 대해 조금 더 고민해봐야겠다.