2579(dp)

첫인상

보자마자 dp 문제였다.

풀이

변수가 연속 여부, 계단의 점수 2개라서 2차원 dp로 문제를 풀어줬다

문제상황

깊게 생각하지 않고 방정식을 짜서 3번이나 틀리게 구현했다 구현 전에 제대로 확인하고 깊게 생각하고 구현해야겠다

코드

#include<iostream>
#include<queue>
using namespace std;

int dp[3][305];
int nums[305];
int sz;

void input() {
	cin >> sz;

	for (int i = 1; i <= sz; i++) {
		cin >> nums[i];
	}
}

void solve() {
	int y = 1;

	dp[1][1] = nums[1];
	dp[1][2] = nums[2];

	while (y < sz) {
		dp[0][y + 1] = max(dp[1][y], dp[2][y]);
		dp[1][y + 1] = dp[0][y] + nums[y + 1];
		dp[2][y + 1] = dp[1][y] + nums[y + 1];
		y += 1;
	}

	cout << max(dp[1][sz], dp[2][sz]);
}

int main() {
	input();
	solve();
}