[백준(BOJ)] 계단 오르기(2579) C++
문제 : BOJ_2579번 계단 오르기
문제 설명
DP
각 계단마다 점수가 있고, 도착 지점까지 계단을 오르며 점수를 더해서 최댓값이 나와야 합니다.
이때 계단은 한 번에 한 계단이나 두 계단씩 오를 수 있고, 세 개의 계단을 연속해서 밟을 수는 없습니다.
그리고 마지막 도착 지점의 계단은 반드시 밟아야 합니다.
Solution
dp를 활용하여 해결하였습니다.
dp[현재 계단 인덱스][이전 계단과 연속해서 밟았는지의 유무] = 현재 계단까지의 최댓값
으로 dp 식을 짜봤습니다.
현재 계단에서 이전 계단과 연속해서 밟지 않았다면, 현재 계단 인덱스-2
의 계단에서의 최댓값을 갱신해 주어야 합니다.
이때 현재보다 2가 낮은 인덱스의 계단은 이전 계단과 연속해서 밟은 경우와 연속해서 밟지 않은 경우 모두 가능하므로 둘 중의 최댓값을 갱신해 주어야 합니다.
현재 계단에서 이전 계단과 연속해서 밟는다면, 이전 계단에서 연속해서 밟지 않은 경우에 현재 계단의 점수를 더해주면 최댓값이 됩니다.
Description
- 첫 번째 계단에 대해선,
dp[1][0]=1번째 계단 점수
,dp[1][1]=0
으로 할당해 주고 시작했습니다.
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int n;
int dp[301][2];
vector<int> adj;
int main(){
cin >> n;
adj.resize(n+1);
for(int i=1; i<=n; i++){
cin >> adj[i];
}
dp[1][0]=adj[1];
dp[1][1]=0;
for(int i=2;i<=n;i++){
dp[i][0]=max(dp[i-2][0],dp[i-2][1]);
dp[i][0]+=adj[i];
dp[i][1]=dp[i-1][0] + adj[i];
}
cout << max(dp[n][0],dp[n][1]) << '\n';
return 0;
}
PREVIOUS[BOJ] 이진 트리(13325)