[백준/BOJ] 2579번 계단 오르기 (C/C++)

백준 온라인 저지(BOJ) 2579번 계단 오르기

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

* 사용언어 : C언어, C++

 

1. 문제

점수가 쓰여진 300개 이하의 계단을 한 계단 or 두 계단 씩 오를 때

지나온 계단의 총 점수의 최대값을 출력

(단, 연속된 세 개의 계단을 밟을 수 없고, 마지막 계단은 반드시 밟아야 함)

 

2. 풀이

bottom-up 방식으로 풀기 위해서 크기가 N * 2인 2차원 배열을 선언했습니다.

 

배열의 i번(1차원) index에 있는 2개의 값은 각각

[① i번 계단에 도착하기 직전에 한 계단을 올라왔을 때의 최대값]과 [② 두 계단 올라왔을 때의 최대값]을 구해서 저장합니다.

그리고 마지막에 dp[N - 1][0]과 dp[N - 1][1] 중 큰 값을 출력하면 됩니다.

 

2차원 배열의 index는 0이면 한 계단, 1 이면 두 계단을 올라온 경우의 최대값을 의미합니다.

 

1) (index == 0) i번 계단에 도착하기 위해 한 계단을 올라온 경우

한 계단을 올라서 i번 계단에 도착했으므로 반드시 i - 1번 계단에서 올라와야 합니다.

즉, dp[i][0] 계산하기 위해 dp[i - 1]의 두 값을 사용하게 됩니다.

 

하지만 이 경우 문제의 2번 조건(연속된 3개의 계단을 밟을 수 없음)에 의해 dp[i - 1][0]을 사용할 수 없습니다.

따라서 아래와 같이 dp[i - 1][1]만을 사용하여 최대값을 계산합니다.

dp[i][0] = dp[i - 1][1] + score[i];

 

2) (index == 1) i번 계단에 도착하기 위해 두 계단을 올라온 경우

두 계단을 올라서 i번 계단에 도착했으므로 반드시 i - 2번 계단에서 올라와야 합니다.

즉, dp[i][1] 계산을 위해 dp[i - 2]의 두 값을 사용하게 됩니다.

 

i번 도달을 위해 두 계단을 올라오기 때문에, i - 2번 계단에 오를 때 한 번에 올라왔든 두 번에 올라왔든 상관이 없습니다.

따라서 아래와 같이 dp[i - 2][0]과 dp[i - 2][1] 두 값 중 큰 값을 사용하여 최대값을 계산합니다.

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

 

위와 같은 방식으로 문제의 예시를 하나 씩 계산해보면 아래와 같은 결과를 얻게 됩니다.

그 외 풀이는 아래 코드로 설명 대체하겠습니다.

2차원 배열 index (1칸 : 0, 2칸 : 1)

 

3. 코드

#ifndef _CRT_SECURE_NO_WARNINGS
#define _CRT_SECURE_NO_WARNINGS
#endif
/*
2579_정수 삼각형
1116KB	0ms
*/
#include <cstdio>

const int LM = 300;
int score[LM], dp[LM][2], N;

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

int main() {
#ifdef _WIN32
	freopen("input.txt", "r", stdin);
#endif // _WIN32
	scanf("%d", &N);
	for (int i = 0; i < N; ++i) scanf("%d", &score[i]);
	
	dp[0][0] = score[0];
	dp[1][0] = score[0] + score[1];
	dp[1][1] = score[1];

	for (int i = 2; i < N; ++i) {
		dp[i][0] = dp[i - 1][1] + score[i];
		dp[i][1] = max(dp[i - 2][0], dp[i - 2][1]) + score[i];
	}

	printf("%d\n", max(dp[N - 1][0], dp[N - 1][1]));
	return 0;
}