[C++] 백준 2579번 풀이 (계단오르기게임)

- 문제 (2579번) : 계단오르기 문제

• 링크 : https://www.acmicpc.net/problem/2579
  
  다음과 같은 규칙을 만족할 때 얻을 수 있는 총 점수의 최댓값을 구하는 프로그램을 작성.

  1. 계단은 한 번에 한 계단씩 또는 두 계단씩 오를 수 있다.
     ( 바로 다음계단 혹은 다다음계단을 오를 수 있다. )
  2. 연속된 세 개의 계단을 모두 밟아서는 안된다.
     ( 단, 시작점은 계단에 포함되지 않는다. )
  3. 마지막 도착 계단은 반드시 밟아야 한다.

---

- 입력 및 출력

[입력]

• 입력의 첫째 줄에는 계단의 개수가 주어짐. ( 계단의 개수 ≤ 300, 자연수 )
• 둘째 줄부터 한줄에 하나씩 제일 아래에 놓은 계단부터 순수대로 각 계단의 점수가 주어짐. (계단의 점수 ≤ 10,000, 자연수)

[출력]

• 게임을 통해 얻을 수 있는 총 점수의 최댓값을 출력

---

- 문제 풀이

• 계단을 하나씩 오르며 max값 update <- DP 활용해 문제 해결
• memoization을 할 때

  1. 계단이 1개일때 : 계단이 1개이므로 첫번째 계단이 max
     
     
  2. 계단이 2개일때 : 첫번째 계단 + 두번째 계단 점수가 max 점수
     (각 계단의 점수는 10,000 이하의 자연수이므로 성립됨.)
     
     
  3. 계단이 3개일때 :
     [첫번째 계단 + 세번째 계단] or [두번째계단 + 세번째 계단] 이 된다.
     ( 게임의 규칙 중 3개의 계단을 연속해 올라갈 수 없고, 마지막계단은 반드시 올라가야 하므로)
     
     
  4. 계단이 4개 이상일 때 : 계단이 4개일때를 생각해보면
     [두번째 계단 + 네번째 계단] or
     [첫번째 계단 + 세번째 계단 + 네번째 계단]
     이 된다.
     
     
     이것을 N개의 계단으로 생각해보면 다음과 같다.

     [N-2 계단까지의 max + N번째 계단] or
     [N-3 계단까지의 max + N-1번째 계단 + N번째 계단]

이 memoization을 통해 코드를 작성하면 다음과 같다.
( input.at(N) : N번째 계단의 점수 , maximum.at(N) : N까지의 최대점수)

• 계단이 1개일때
  

• 계단이 2개일때
  

• 계단이 3개일때
  

• 계단이 4개 이상일때
  

---

- 최종 코드