[C] 백준 - 2579번: 계단 오르기

3월 14일(화) - 동적계획법 1 (2579번)

2579번: 계단 오르기

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

 

최초 생각 정리

- 각각의 계단에 쓰여있는 점수는 stairs[301]배열에 입력받고, 최댓값은 dp[301]배열에 저장한다

- dp[1]에는 첫 번째 계단의 점수가 그대로 들어가므로 dp[1] = stairs[1]

- dp[2]에는 첫 번째와 두 번째 계단을 모두 밟는 경우의 점수가 최대가 되므로 dp[2] = stairs[1] + stairs[2]

- dp[3]부터는 반복문안에서 점화식을 세워서 최댓값을 고려해야한다

  dp[3]을 구하려면 세 번째 계단이 2가지 상황 중 어느 position의 상황에서 더 큰 점수를 가지는지를 비교해야한다

 

- 조건에 의해서 연속으로 밟을 수 있는 계단은 2개이다

  따라서 세 번째 계단이 연속된 2개의 계단 중 첫 번째 계단인 position 인지

  아니면 연속된 2개의 계단 중 두 번째 계단인 position 인지를 나누어서 계산해야한다

- 연속된 2개의 계단 중 첫 번째 계단인 position 이라면

  stairs[i]값에다가, 이전의 연속된 2개의 계단의 합인 dp[i-2]를 더해야하고,

- 연속된 2개의 계단 중 두번째 계단인 position 이라면

  stairs[i]값에다가, 이전의 연속된 2개의 계단의합인 dp[i-3]를 더하고,

  + 지금의 연속된 2개의 계단 중 첫 번째 계단인 stairs[i-1]값까지 추가적으로 더해야한다

 

- 위의 2가지 상황 중 더 큰 값인 경우를 dp[i]에 저장하면 된다

- 이러한 점화식 관계를 가장 먼저 dp[3]에 적용하려면 dp[0]값도 필요해지기에 dp[0] = 0 도 추가

- 마지막에 stairs[num_stairts]를 밟아서 나오는 값인 dp[num_stairs]를 최종적으로 출력

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

 

문제점

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

 

풀이

#define _CRT_SECURE_NO_WARNINGS
#pragma warning(disable: 4996)

#include <stdio.h>

int MAX(int x, int y)
{
	return ((x > y) ? x : y);
}

int main(void)
{
	int stairs[301] = { 0, };
	int dp[301];

	int num_stairs;
	scanf("%d", &num_stairs);
	for (int i = 1; i < num_stairs + 1; i++)
	{
		scanf("%d", &stairs[i]);
	}

	dp[0] = 0;
	dp[1] = stairs[1];
	dp[2] = stairs[1] + stairs[2];
	for (int i = 3; i < num_stairs + 1; i++)
	{
		dp[i] = stairs[i] + MAX(dp[i - 2], stairs[i - 1] + dp[i - 3]);
	}

	printf("%d", dp[num_stairs]);
	return 0;
}

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ