[C언어] 백준 2579 : 계단 오르기

생각의 흐름

모르겠다. dp파트니까 저장하면서 가는건 당연할거고, 입력값 계속 더해주면서 최대값 계산해주는건 알겠는데, 점화식을 모르겠다.
이전 문제들처럼 그래도 좀 명확했었으면 좋겠는데 2칸점프, 3연속계단은 안되고... 어떻게 점화식을 세울지 규칙을 못찾았다.

검색을 해서 점화식만 힌트를 얻었다.

예를 들어 4칸이라고 가정해보자,
OOXO OXOO XOXO 이렇게 마지막 계단을 밟는다는 조건이 있기에, 경우의 수는 이렇게 나온다.
하지만 우리는 최대값을 구한다. 따라서 OOXO, XOXO중엔 무조건 OOXO가 크다. 그래서 두가지로 분류할 수 있다.

OOXO -> 마지막 직전의 계단을 안밟았다. 따라서 마지막 전전계단까지의 최대값을 구하고, 마지막 계단의 값을 더해주면 된다. -> dp[i] = dp[i - 2] + input[i]
OXOO -> 마지막 직전의 계단을 밟았다. 따라서 마지막 전전전계단까지의 최대값을 구하고, 마지막 전 계단, 마지막 계단을 더해주면 된다. -> dp[i] = input[i - 1] + input[i], dp[i - 3]

내가 푼 코드

#include <stdio.h>

int max(int a, int b)
{
	return a > b ? a : b;
}

int main()
{
	int i, n;
	int input[301];
	int dp[301];
	scanf("%d", &n);
	i = 1;
	while (i <= n)
	{
		scanf("%d", &input[i]);
		i++;
	}
	dp[1] = input[1];
	dp[2] = input[1] + input[2];
	i = 3;
	while (i <= n)
	{
		dp[i] = max(dp[i - 2] + input[i], dp[i - 3] + input[i - 1] + input[i]);
		i++;
	}
	printf("%d", dp[n]);
}

점점 dp도 익숙해져간다.