[BOJ] 2579번 계단오르기 풀이(C++)

2017.10.25에 쓰여진 글입니다.

---

 

문제링크

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

2579번: 계단 오르기

 

풀이방법

뭐 딱히 풀이방법이라고 하면..

dp의 풀이는 역시나 점화식을 이쁘게 세워보는것.. 뒤부터 생각해보는 것 정도...

코드와 주석을 보고 열심히 이해하시면 될듯!

 

소스코드

#include <iostream>
#include <algorithm>
 
using namespace std;
 
int N;   //계단의 개수
int s[301];      //계단의 각 점수 저장
 
int main()
{
   int dp[301] = { 0 };
   //dp[0] = 0번째계단에서의 최대점수
   //dp[1] = 1번째계단에서의 최대점수
   //...
   //dp[N] = N번째 계단에서의 최대점수
   cin >> N;   //계단의 개수 입력받기
   for (int i = 1; i <= N; i++)
      cin >> s[i];
   dp[0] = 0;      //초기 바닥일때 0 넣어줌
   dp[1] = s[1];   //한칸 올라옴 (첫번째 계단의 점수)
   dp[2] = max(s[1] + s[2], s[2]);   //두번째 계단올라오는법 -> 더큰거(계단2개밟고올라오기,한번에 2번째계단으로 점프)
   for (int i = 3; i <= N; i++)
      dp[i] = s[i] + max(s[i - 1] + dp[i - 3], dp[i - 2]);      
   //현재 계단의 점수 + 큰거(3칸전->1칸전->현재, 2칸전에서 한번에 뜀)
   //만약 현재자리한칸전의 계단에서 뛸려면 무조건 3칸전->1칸전->현재 의 순으로 뛰어야만 한다.
   //3칸전 1칸전 현재 -> 연달아 3번을 밟을수없기때문에 3칸전까지 뛸수있는 최대값 + 1칸전 계단점수+현재계단점수
   //2칸전에서는 무조건 한번에 뛰어야한다. (위에 1칸전 상황과 중복방지)
   cout << dp[N] << endl;   //N번째 계단에서 최대값을 저장한다.
 
   return 0;
}