BAEKJOON 2579: 계단 오르기 for C

 계단 오르기

2579번: 계단 오르기

---

설명

 DP 공부를 하면서 느낀건데, 규칙성이 있다면 점화식을 구하는게 급선무?라 생각한다. 일단, 문제에서 규칙을 정해주었기 때문에 규칙을 보면 다음과 같다.

 여기에서 중요한 것이 (3)인데, 마지막에 대한 설명이 존재하기 때문이다. 따라서 마지막 규칙을 기반으로 하면 다음과 같다.

dp[i] = dp[i - 3] + data[i - 1] + data[i];
dp[i] = dp[i - 2] + data[i];

 배열 dp는 여태 계산상에서 가장 높은 수를 찾은 데이터를 담은 배열[# 순수 데이터의 연산 결과를 담고 있다]이다. 배열 data는 입력으로 받은 순수 데이터이다. i번째가 마지막 인덱스라고 할 때, 마지막 인덱스 i에는 앞서 언급한 (1)과 (2)규칙이 적용되어야 한다. 따라서 연속된 3개의 데이터가 존재할 수 없다.

 이미지를 볼 때, i가 가장 마지막에 위치하므로, dp접근과 더불어 data에서도 연속된 인덱스에 접근해서는 안된다.

 배열 dp의 경우엔 모든 연산에서 자기 자신에 해당하는 data 값을 연산에 포함하고 있다. 따라서, i가 3일때를 기준으로 했을 때 다음과 같다.

dp[3] = dp[0] + data[1] + data[3];
dp[3] = dp[1] + data[3];

 그러므로 dp와 data를 포함해 어느 배열에서도 세 번 연속된 인덱스에 접근해서는 안된다.

 

---

코드

#include <stdio.h>

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

int main(void) {
	int n;
	scanf("%d", &n);

	int data[300], dp[300];

	for (int i = 0; i < n; ++i) scanf("%d", data + i);

	dp[0] = data[0];
	dp[1] = data[0] + data[1];
	dp[2] = max(data[0], data[1]) + data[2];

	for (int i = 3; i < n; ++i) dp[i] = max(dp[i - 3] + data[i - 1], dp[i - 2]) + data[i];

	printf("%d", dp[n - 1]);

	return 0;
}

 여기에서, 배열 dp의 첫 시작 부분인 인덱스 0-2의 값을 구할 때는, 각 위치에서 가장 높은 수를 구하도록 하면 된다.

• dp[0] : 시작이므로 data[0]의 값만 가질 수 있음
• dp[1] : 뒤에 나오는 값이 dp[0]뿐이므로 둘을 더한 값이 최대
• dp[2] : 3연속 더할 수는 없으므로, data[0]과 data[1]중 높은 것을 data[2]와 더한 것이 최대