BaekJoon 2579번: 계단 오르기

풀이법

1) n의 수가 작다면 Backtracking으로 풀 수 있는 문제이지만 현재 n이 300까지 나올 수 있기에 DP로 푸는 것이 좋다.

2) 점화식을 구현한다면 누구나 쉽게 풀 수 있는 문제라고 생각한다.

    단순한 1차원 배열로는 해당 문제에 대한 점화식을 도출하는 것이 쉽지 않을 것이라 생각한다.

    해당 값이 연속된 계단인지 아닌지를 확인할 수 있는 점화식을 도출하는 것이 핵심이다.

   

    arr[i] : i번째 계단에 대한 입력 값

 

    ans[i][0] : i 번째 계단을 밟았지만 연속된 계단이 아닐 때

    ans[i][1] : i 번째 계단을 밟았는데 연속된 계단일 때

 

    ans[i][0] = max(ans[i - 2][0], ans[i - 2][1]) + arr[i];
    ans[i][1] = ans[i - 1][0] + arr[i];

    

    최종 값 : max(ans[n][0], ans[n][1])

 

    

    예시에 있는 입력의 경우

   

   다음과 같은 결과를 도출하여 정답에 도달할 수 있다.

#include <iostream>
#include <vector>
#include <algorithm>
#include <stdio.h>
#include <cstring>
using namespace std;

int n;
vector<int> arr;
int ans[301][2];
void dp()
{
	ans[1][0] = arr[1];
	ans[1][1] = 0;
	ans[2][0] = arr[2];
	ans[2][1] = arr[1] + arr[2];
	for (int i = 3; i <= n; i++)
	{
		ans[i][0] = max(ans[i - 2][0], ans[i - 2][1]) + arr[i];
		ans[i][1] = ans[i - 1][0] + arr[i];
	}
	cout << max(ans[n][0], ans[n][1]);
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> n;
	arr.push_back(0);
	for (int i = 0; i < n; i++)
	{
		int a;
		cin >> a;
		arr.push_back(a);
	}
	dp();
}

한계점 및 개선사항 (+주의사항)

빠르게 필요한 점화식을 세우기 위해서는 여러 방법으로 배열을 채워가는 연습이 필요할 것 같다.

 

github.com/pearlcrum/CodingTest/tree/main

pearlcrum/CodingTest