2579 - 계단 오르기

문제풀이/백준

동바리 2021. 6. 22. 21:38

	#include <iostream>

	using namespace std;

	int max_return(int, int);

	int main(void)
	{
	int stair_size = -1;

	cin >> stair_size;

	int* stair = new int[stair_size];
	int* dp = new int[stair_size];

	for(int i =0; i < stair_size ; i++) {
	cin >> stair[i];
	}

	dp[0] = stair[0];
	dp[1] = max_return(stair[1], stair[0] + stair[1]);
	dp[2] = max_return(stair[0] + stair[2] , stair[1] + stair[2]);

	for(int i = 3; i < stair_size; i++) {
	dp[i] = max(stair[i] + dp[i-2], stair[i] + stair[i-1] + dp[i-3]);
	}

	cout << dp[stair_size - 1] << endl;

	delete [] stair;
	delete [] dp;

	return 0;
	}

	int max_return(int src1, int src2)
	{
	return src1 > src2 ? src1 : src2;
	}

view raw 2579.cpp hosted with ❤ by GitHub

동적 계획법 개념을 파악해서 풀어야 하는 문제이다.

또한 메모이제이션(memoization) 기법이 들어간다.

위의 코드는 공통적인 사항을 추상화해서 점화식으로 표현하였고 그것을 이용해 코딩한것이다.

[백준 2579번] 계단 오르기

DP로 분류된 문제 조건 1. 계단을 오를때는 1칸 또는 2칸까지 한번에 오를수있다. 2. 연속된 3칸은 오를 수 없다. 3. 마지막 계단은 무조건 밟아야한다. 풀이 마지막 계단을 무조건 밟아야한다면 두가지로 분류할..

kwanghyuk.tistory.com

풀이 참조는 이 분의 것을 많이 참고하였다.