[BOJ] 2579 - 계단 오르기

안녕하세요.

여행벌입니다.

BOJ 2579 DP 문제인 계단오르기 풀이를 해보겠습니다.

---

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

2579번: 계단 오르기

[알고리즘설계]

2차원 배열 dp[2][N]을 선언해

[0][i] : i번 째 계단까지 오르는데 1칸을 점프해서 오를 때의 최대값. (i - 1번 째에서 올라온 경우)

[1][i] : i번 째 계단까지 오르는데 2칸을 점프해서 오를 때의 최대값. (i - 2번 째에서 올라온 경우)

(i - 1) 계단에서 점프하는 경우는 연속된 세 계단을 밟으면 안되므로,

2칸 점프해서 올라온 i-1의 최대값을 참조하고,

2칸 점프해서 i번 째 계단에 오른 경우의 최대 값은

1칸 점프해서 오른 i - 2 최대값과 2칸 점프해서 올라온 i - 2 최대값 중 더 큰 값을 참조합니다.

#include<iostream>
#include<algorithm>

using namespace std;

int input[301];

// list[x][y]
// y번째 계단에 (x+1)만큼 점프해서 온 최대값.
int list[2][301];

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0);

	int n;
	cin >> n;
	for (int i = 1; i <= n; i++)
		cin >> input[i];
	list[0][1] = input[1];
	list[0][2] = input[1] + input[2];
	list[1][2] = input[2];

	for (int i = 3; i <= n; i++) {
		list[0][i] = list[1][i - 1] + input[i];
		list[1][i] = max(list[1][i - 2], list[0][i - 2]) + input[i];
	}
    cout << max(list[0][n], list[1][n]);

}

---

열심히 공부하고 노력하고 있는 꿈 많은 예비 개발자입니다.

혼자서 공부한 내용을 정리하고 포스팅하다 보니 틀린 내용이 있을 수도 있습니다.

많은 조언과 가르침 주실 분은 댓글로 자유롭게 남겨주셔도 좋을 것 같습니다! 

감사합니다.