백준 2579번 : 계단 오르기 (DP)

 

문제 링크

 

 

 

C++코드

#include <bits/stdc++.h>
using namespace std;

int s[305];
int n;
int d[305][2]; // 강의 내에서 설명은 1-indexed로 했지만 메모리 절약을 위해 0-indexed로 구현했습니다. 
int main(void){
  ios::sync_with_stdio(0);
  cin.tie(0);
  cin >> n;
  for(int i = 0; i < n; i++) cin >> s[i];
  if(n==1){ // 뒤의 코드를 보면 알겠지만 d[1][0], d[1][1]에서 s[1]을 참조하는데 만약 n = 1이면 참조하면 안되는 값을 참조하는 것이므로 n = 1일때를 따로 예외처리합니다.
            // 그러나 바람직한 코드는 아니지만 사실 이 예외처리를 하지 않아도 n=1일 때 답은 올바르게 나옵니다. 이유는 직접 한 번 생각해보세요.
    cout << s[0];
    return 0;
  }
  d[0][0] = s[0];
  d[0][1] = 0; // 사실 애초에 d가 전역변수로 0으로 초기화되어있어서 굳이 안해줘도 되지만 헷갈릴까봐 추가했습니다.
  d[1][0] = s[1];
  d[1][1] = s[0]+s[1];
  for(int i = 2; i < n; i++){
    d[i][0] = max(d[i-2][0],d[i-2][1])+s[i];
    d[i][1] = d[i-1][0]+s[i];
  }
  cout << max(d[n-1][0],d[n-1][1]);
}