[백준/BOJ] 2579 - 계단 오르기 (c++) (DP)

1. 문제

 

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

---

2. 풀이

이 문제는 DP를 이용해 푸는문제이다.

 

dp[i]는 i번째 계단은 밟고, 1부터 i번째까지 최대의 수이다.

 

즉 dp[i]는 그 바로 전단계의 계단을 밟은 여부에 따라 바뀌는 것이다.

 

(시작) dp[0] = 0

 

dp[1] = arr[1]

 

dp[2] = arr[1] +arr[2]

 

(3≤i≤n) dp[i] = max(dp[i-2] + arr[i], dp[i-3] + arr[i-1] +arr[i])이다.

 

 

 

cf)

 

https://zcacoding.tistory.com/20

[백준/BOJ] 2156 - 포도주 시식 (c++) (DP)

이 문제는 포도주 시식과 비슷하면서 다르다.

 

위의 백준 2156번 포도주 시식과 이 문제의 차이점을 말해보자면

 

포도주 시식도 자기자신의 포도주를 먹었다고 가정하에 한다면

 

dp[i] = max(dp[i-2] + arr[i], dp[i-3] + arr[i-1] +arr[i])라는 식이 나온다.

 

하지만 포도주는 2칸을 뛰고 먹어야 최대가 나오는 상황이 나오지만

 

계단은 최대 1칸만 건너뛰고 올라가야된다는 조건이 있다. 따라서 dp[i-1]을 생각하지않는 것이다.

---

3. 소스코드

#include <iostream>

using namespace std;

int n, arr[301], dp[301];

int main() {
	cin >> n;
	for (int i = 1; i <= n; i++) cin >> arr[i];

	dp[0] = 0;
	dp[1] = arr[1];
	dp[2] = arr[1] + arr[2];

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

	cout << dp[n];
}

---

4. 참고

 

---

질문, 고칠점 등 댓글 언제나 환영입니다.