문제 풀이/백준
BOJ 2579번: 계단 오르기
danbibibi
2022. 11. 30. 17:38
문제
문제 바로가기> BOJ 2579번: 계단 오르기
2579번: 계단 오르기
계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. <그림 1>과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점
www.acmicpc.net
풀이
주어진 조건을 만족하면서 다음 계단에 도착하는 방법은 다음과 같이 총 2가지이다.
1. 두 계단 전에서 현재 계단으로 : dp[i-2]+arr[i]
2. 한 계단 전에서 현재 계단으로 : dp[i-3]+arr[i-1]+arr[i]
따라서 위 점화식을 토대로 max 값을 찾아내면 된다!
#include<iostream>
#define MAX 301
using namespace std;
int N;
int arr[MAX], dp[MAX];
void input(){
cin >> N;
for(int i=1; i<=N; i++) cin >> arr[i];
}
void solution(){
dp[1] = arr[1];
dp[2] = arr[1] + arr[2];
for(int i=3; i<=N; i++) dp[i] = max(dp[i-2]+arr[i], dp[i-3]+arr[i-1]+arr[i]); // 두 계단 점프 or 한 계단 점프
cout << dp[N]; // 계단 오르기 게임에서 얻을 수 있는 총 점수의 최댓값
}
int main(){
ios_base::sync_with_stdio(0); cin.tie(0);
input();
solution();
}