백준 2579번 계단 오르기

< 백준 2579번 계단 오르기 - 마포 코딩박 >

사용한 알고리즘: DP


 계단을 1칸, 혹은 2칸 오를 수 있고 연속된 3칸의 계단을 연속으로 밟아서는 안됩니다. 각 계단 칸을 밟을 때 해당 칸의 점수를 얻을 수 있습니다. 이때 마지막 칸에 도착했을 때 얻을 수 있는 최대 점수를 구하는 문제였습니다.

문제풀이는 다음과 같습니다.

(1) (코드 5~7)
 'dp[x][0] : 1칸 올라와서 x칸 도착했을 때 점수 최댓값' ,
 'dp[x][1] : 2칸 올라와서 x칸 도착했을 때 점수 최댓값' 으로 설정했습니다.

(2) (코드 12~15)
 dp[1][0] = A[1] : 1칸 올라와서 1계단에 도착했을 때 얻을 수 있는 점수 최댓값
 dp[2][0] = A[1]+A[2] : 1칸 올라와서 2계단에 도착했을 때 얻을 수 있는 점수 최댓값
 dp[2][1] = A[2] : 2칸 올라와서 2계단에 도착했을 때 얻을 수 있는 점수 최댓값
 위와같이 초기값을 설정합니다.

(3) (코드 17~20)
 초기값을 바탕으로 dp 값을 계산해줍니다.
 연속해서 3칸을 밟을 수 없기 때문에 dp[x][0] = dp[x-1][1]+A[x] 입니다.
 즉 x-1칸에서 1칸 올라와서 x칸을 밟으려면 x-1칸은 2칸올라와서 도착했어야 합니다.

	#include <bits/stdc++.h>
	using namespace std;
	int T, A[333];
	// dp[x][0] : 1칸 올라와서 x칸 도착했을 때 점수 최댓값
	// dp[x][1] : 2칸 올라와서 x칸 도착했을 때 점수 최댓값
	int dp[333][2];
	int main(){ios_base::sync_with_stdio(false); cout.tie(NULL); cin.tie(NULL);
	cin >> T;
	for (int i = 1; i <= T; ++i) cin >> A[i];
	// 초기값 설정
	dp[1][0] = A[1];
	dp[2][0] = A[1]+A[2];
	dp[2][1] = A[2];
	for (int i = 3; i <=T; ++i){
	dp[i][0] = dp[i-1][1]+A[i];
	dp[i][1] = max(dp[i-2][0],dp[i-2][1])+A[i];
	}
	cout << max(dp[T][0],dp[T][1]) << '\n';
	return 0;
	}

view raw BOJ 2579.cpp hosted with ❤ by GitHub