백준 2579 계단 오르기

https://www.acmicpc.net/problem/2579

문제와 채점은 위 사이트에서 확인 하실 수 있습니다

 

이 문제는 계단을 오르는데 1칸 또는 2칸을 이동 할 수 있습니다. 그런데 3칸의 계단을 연속해서 오를 수 없을때 마지막 계단에 도달하는 최대값을 구하는 문제입니다. 각계단마다 점수가 있기 때문에 dp를 이용하여 이전 계단들 까지의 값을 이용하여 마지막 계단의 값을 구하여야 합니다.

따라서 저는 2차원 배열을 선언해 0번은 바로이전 계단에서 올라온 상태이고 1번은 2칸 아래의 계단에서 올라온 상태로 정하고 계산을 하였습니다.

 

dp[1][i] 같은경우는 i-2번째 계단에서 2칸을 이동했을 때 값이므로 이때는 dp[0][i-2] 와 dp[1][i-2] 중 더큰 값에다 계단의 값을 더해주어서 넣어주면 됩니다.

dp[0][i] 같은경우 i-1번째 계단에서 1칸을 이동한 경우이므로 i-1번째 계단은 반드시 i-3번째 계단에서 2칸을 올라온 값이여야 합니다. 따라서

dp[1][i-1] 의 값에 계단의 값을 더해주면 됩니다.

 

다음은 코드입니다.

 

#include <iostream>

using namespace std;

int main(void) {
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	int stairs[301] = {0, };
	int dp[2][301] = {0, };
	int n; cin >> n;
	for(int i = 1; i <= n; i++)
		cin >> stairs[i];
	dp[0][1] = stairs[1]; //0번은 이전에 한칸 이동 
	dp[1][2] = stairs[2]; // 1번은 이전에 두칸이동으로 도착 
	dp[0][2] = stairs[1] + stairs[2];
	for(int i = 1; i <= n-1; i++) {
		if(i <= n-2)
			dp[1][i+2] = max(dp[1][i], dp[0][i]) + stairs[i+2];
		
		if(i != 1) 
			dp[0][i+1] = dp[1][i] + stairs[i+1];
		
	}
	cout<<max(dp[0][n], dp[1][n]);
	return 0;
}