계단 오르기

문제 링크

솔직히 지금까지의 문제들은 점화식이 상당히 직관적인 편에 속했다. 이제 슬슬 문제들 난이도가 올라간다.

풀이 1 : 클래식 풀이

이전 RGB거리 문제에서처럼 2칸 뛴 최적값과 1칸 뛴 최적값을 별도로 저장해가며 정답을 구할 수 있다. 연속한 3계단은 밟을 수 없으므로 1칸 뛴 최적값을 구할 때는 이전에 2칸 뛴 최적값만 사용하고 2칸 뛴 최적값을 구할 때는 이전의 두가지 경우 모두 사용하는 식으로 답을 구할 수 있다.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
struct s {
    int o = 0, t = 0; // o : 1칸 뛴 최적값 t : 2칸 뛴 최적값
};
int main()
{
    int n; cin >> n;
    vector<int> arr(n + 1); vector<s> dp(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> arr[i];
    }
    dp[1].o = arr[1];
    dp[1].t = arr[1];
    for (int i = 2; i <= n; i++) {
        dp[i].o = dp[i - 1].t + arr[i]; // 1칸 뛴 경우 계산
        dp[i].t = max(dp[i - 2].t, dp[i - 2].o) + arr[i]; //2칸 뛴 경우 계산 
    }
    cout << max(dp[n].o, dp[n].t);
    return 0;
}

풀이 2 : 기교 풀이

이전 01타일 문제에서처럼 계단을 밟는 방법 조합의 최소 단위를 파악해보자. 연속한 3계단은 밟을 수 없으므로 ==1칸만 뛰었다면 그 다음에는 반드시 두칸을 뛰어야만 한다.== 따라서 1칸을 뛴 다음 2칸을 뛰는 것과 2칸 뛰는 것 2가지가 선택할 수 있는 최소 행동 단위가 된다.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
	int n; cin >> n; vector<int> arr(n + 1), dp(n + 1);
	for(int i=1;i<=n;i++) {
		cin >> arr[i];
	}
	dp[1] = arr[1];
	dp[2] = arr[1] + arr[2]; // 시작 계단은 연속한 계단수에 포함하지 않으므로 기저 사례 입력 가능;
	for(int i=3;i<=n;i++) {
		int s1 = arr[i - 1] + dp[i - 3] + arr[i]; // 한칸 뛰고 두칸 뛰기
		int s2 = dp[i - 2] + arr[i]; // 두칸 뛰기
		dp[i] = s1 > s2 ? s1 : s2; // 둘 중 큰 거 고르기
	}
	cout << dp[n];
	return 0;
}