백준, boj) 2579. 계단 오르기 ( C / C++ )

1. 문제 링크

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

2579번: 계단 오르기

2. 문제 개요

각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점수를 얻게 된다.

 

3. 문제 힌트

연속된 세 계단을 가면 안된다는 조건이 없으면 정말 쉬운 문제이다.

이것을 어떻게 구현할 것인지가 키포인트이다.

 

따라서 어떤칸 n번째에 도착했을 때,  몇 번 연속으로 걸어왔는지 체크하는 게 필요하다.

 

 

4. 문제 풀이

 

dp[n][m]에서 n은 몇 번째 계단에 있는지 체크한다. m은 몇 번 연속으로 왔는지 체크한다.

3번 연속 밟으면 안 되니까 dp [n][2]까지만 선언해준다.

 

따라서 초기값을 설정해주고,

1번째 계단은 1칸걸어올라간 단 1개의 경우만 있으므로 초기치를 설정해준다.

dp[1][0] = score[1];

두 번째 배열이 0인 것은 1번 연속,

두 번째 배열이 1인 것은 2번 연속을 의미한다.

 

따라서 N번째일 때는 어떻게 되는지 알아보자

N번째 계단을 1칸 올라와서 도착했다고 하자.

dp [n][1] = dp [n-1][0] +score [n] 이 될 것이다.

 

N번째 계단을 이번에는 2칸 올라와서 도착했다고 하자.

dp [n][0] = (dp [n-2][0] or dp [n-2][1]) + score [n]이 될 것이다.

 

dp는 각 위치에서의 최댓값을 갖고 있으므로,

N번째 계단에서의 최대 점수를 나타내는 점화식은

dp[N][1] = dp[N-1][0] + score[N];
dp[N][0] = max(dp[N-2][0], dp[N-2][1]) + score[N]

그래서 값을 출력할 때는 마지막 칸에 도착했을 때 1번 연속으로 온 것이 최대인지, 2번연속으로 온것이 최대인지만 구별해서 출력해주면 된다.

 

ans = max(dp[N][0], dp[N][1])

 

5. 코드

bottom up

#include <cstdio>
#include <algorithm>
using namespace std;

int score[301];
int dp[301][2];

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

	for (int i = 1; i <= n; ++i)
		scanf("%d", &score[i]);

	dp[1][0] = score[1];

	for (int i = 2; i <= n; ++i)
	{
		dp[i][1] = dp[i - 1][0] + score[i];
		dp[i][0] = max(dp[i - 2][1], dp[i - 2][0]) + score[i];
	}
	printf("%d", max(dp[n][0], dp[n][1]));
	return 0;
}

 

top down

#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;

int score[301];
int dp[301][2];

int solve(int cur, int cnt)
{
	int &cache = dp[cur][cnt];
	if (cache != -1) return dp[cur][cnt];

	if (cnt == 0)
		return dp[cur][0] = max(solve(cur - 2, 0), solve(cur - 2, 1)) + score[cur];
	else if (cnt == 1)
		return dp[cur][1] = solve(cur - 1, 0) + score[cur];
}
int main(void)
{
	int n;
	scanf("%d", &n);

	for (int i = 1; i <= n; ++i)
		scanf("%d", &score[i]);

	memset(dp, -1, sizeof(dp));
	dp[0][0] = dp[0][1] = 0;
	dp[1][0] = score[1];

	printf("%d", max(solve(n,0), solve(n,1)));
	return 0;
}

지적, 댓글 언제나 환영입니다~