https://www.acmicpc.net/problem/2579
2579번: 계단 오르기
계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. <그림 1>과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점
www.acmicpc.net
백준 2579 번은 dynamic programming을 사용해서 풀어야 한다
dp를 하면서 느낀거는 점화식을 세우는 게 중요한거 같다.
일단 이 문제의 경우 기준은 마지막 계단이다.
마지막 계단을 올라가는 방법은 2가지가 있다
연속된 3계단을 올라갈 수 없으니 전계단과 전전전계단을 밟고 올라오는 경우의 수와
전전계단을 밟고 마지막 계단에 도착하는 경우의 수가 있다
이경우 점화식은 2개가 존재한다
이를 위해 i번째 계단까지 올라왔을 때의 최댓값을 저장해줄 dp 배열
각계단의 점수 값을 기록해줄 stair 배열을 생성해준다.
dp[i-3]+stair[i-1]+stair[i]
dp[i-2]+stair[i]
이렇게 2개가 있다
그리고 이점화식은 i가 3이상 일 때 부터 작동한다
이에 우리의 dp[0],dp[1],dp[2]는 반복문에 들어가기전에 미리 값을 삽입해 놓아야 한다.
#include <iostream>
using namespace std;
int max(int x, int y)
{
return x > y ? x : y;
}
int main() {
int inputn = 0;
int stair[301] = { 0, };
int dp[301] = { 0, };
cin >> inputn;
for (int i = 0; i < inputn; i++) {
cin >> stair[i];
}
dp[0] = stair[0];
dp[1] = max(stair[1] + dp[0],stair[1]);
dp[2] = max(stair[2]+stair[1], dp[0]+stair[2]);
for (int i = 3; i < inputn; i++) {
dp[i] = max(stair[i] + stair[i - 1] + dp[i - 3], dp[i - 2] + stair[i]);
}
cout << dp[inputn-1];
}