계단 오르기

20 July 2019

문제 : https://www.acmicpc.net/problem/2579

이번은 i번째 계단에 오를 때, 몇 개의 연속한 계단을 올랐는지를 고려하는 문제를 풀어보도록 하겠습니다.

#include<stdio.h>

#define MAX(a,b) (((a)>(b))?(a):(b))

static int** arr;

int main(void) {

	int N, val;

	scanf("%d", &N);

	arr = new int*[N];

	for (int i = 0; i < N; i++)
	{
		scanf("%d", &val);
		
		arr[i] = new int[2];

		if (i == 0)
		{
			arr[i][0] = val;
			arr[i][1] = val;
		}
		else if (i == 1) {
			arr[i][0] = val;
			arr[i][1] = arr[i - 1][0] + val;
		}
		else {
			arr[i][0] = MAX(arr[i - 2][1], arr[i - 2][0]) + val;
			arr[i][1] = arr[i - 1][0] + val;
		}
	}

	printf("%d\n", MAX(arr[N-1][0], arr[N-1][1]));

	return 0;
}

먼저 문제의 조건을 보도록 하겠습니다.
계단은 한칸 또는 두칸씩 오를 수 있고, 대신 연속으로 세칸을 오를 수는 없습니다.
즉, 두칸을 오르는 경우는 그 다음 칸에서 한칸과 두칸을 모두 오를 수 있고, 한칸을 오르는 경우는 그 다음 칸에서 한칸만 오를 수가 있습니다.
해당 칸에서 연속 두칸을 사용하였는지 아닌지, 혹은 앞으로 한칸을 더 오를 수 있는지 없는지를 표시하기 위해 배열로 아래와 같이 작성해보도록 하겠습니다.



arr[i][0] = 연속 두칸을 사용하지 않은 경우 = 이전 칸이 두 칸 전일 때
arr[i][1] = 연속 두칸을 사용한 경우 =  이전 칸이 한칸 전일때

arr[i][0] = MAX(arr[i - 2][1], arr[i - 2][0]) + val;
arr[i][1] = arr[i - 1][0] + val;

위 코드에서 살펴보면, 바로 앞 칸이 두칸 전일때는 해당 칸에서 연속이든 아니든 상관이 없기때문에 연속일때 최대값(arr[i][1])과 연속이 아닐때 최대값(arr[i][0])을 모두 찾아와 비교하게 됩니다.
바로 앞칸이 한칸 전일때는 연속이지 않은 칸만을 이어서 오를 수 있으므로 연속이 아닐때 최대값(arr[i][0])을 가져와 최대값을 설정하도록 합니다.
마지막 칸까지 업데이트하고 나서 두개 중에 최대인 값을 출력해주도록 합니다.