문제

문제 링크

해설

• '시작점'이 따로 있다는 점, '도작점'을 반드시 밟아야 한다는 점은 놓치기 쉬운 조건입니다. 반드시 챙겨야 합니다.
• 연속해서 3개의 계단을 오를 수 없습니다.
  • 즉, 어떤 i번째 계단을 올랐을 때, 연속해서 1개 오른 상태, 연속해서 2개 오른 상태, 연속해서 3개 오른 상태를 구분해야 합니다.
  • DP[N][3]으로 어떤 칸의 3가지 상태를 구분할 수 있도록 메모이제이션 배열을 만듭니다.
• '시작점'이 따로 있다는 점을 주의해야 합니다.
  • 1번칸부터 시작할 경우, 무조건 1번 계단을 포함하게 됩니다.
  • 시작점에서 2칸을 건너는 경우가 최적해일 수도 있기 때문에 0번 계단을 시작점으로 삼아야 합니다.
  • 0번 계단, 0개 오른 상태에서 시작해서 재귀 함수를 시작하면 되겠습니다.
• 1칸을 건넜을 경우, 연속해서 오른 상태이므로 상태를 1 증가해야 합니다.
• 2칸을 건넜을 경우, 연속이 끊어지므로 상태가 1부터 시작합니다.

코드

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

int N, A[301], DP[301][3];

int go(int here, int cnt) {
	if (cnt > 2 || here > N) return -1e9;
	if (here == N) return A[N];
	if (DP[here][cnt]) return DP[here][cnt];
	return DP[here][cnt] = max(go(here + 1, cnt + 1), go(here + 2, 1)) + A[here];
}

int main() {
	cin.tie(0)->sync_with_stdio(0);
	
	cin >> N;
	for (int i = 1; i <= N; ++i) cin >> A[i];
	
	cout << go(0, 0);
}

소스코드 링크

결과