Guest User

Untitled

a guest
Aug 15th, 2018
71
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 0.90 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #define max(a, b) ((a) > (b) ? (a) : (b))
  4. using namespace std;
  5.  
  6. int main(void) {
  7. int n; cin >> n;
  8. vector<int> v(n);
  9. vector<vector<int>> dp(n, vector<int>(2));
  10. for (int i = 0; i < n; i++) cin >> v[i];
  11.  
  12. // 0이면 1번연속, 1이면 2번연속
  13. dp[0][0] = v[0];
  14. dp[1][0] = v[1];
  15. dp[1][1] = v[0] + v[1];
  16.  
  17. for (int i = 2; i < n; i++) {
  18. // [i - 2]번째 계단에서 i번 계단으로 올때, i - 2의 상태는 중요하지 않음
  19. // i - 2까지 한번에 온경우와 2번밟고 온 경우 비교해서 더큰숫자를 저장
  20. dp[i][0] = max(dp[i - 2][0] + v[i], dp[i - 2][1] + v[i]);
  21.  
  22. // [i - 1]번째 계단에서 i번째 계단에 오려면 i - 1계단까지 1번에 온경우 만 가능
  23. // i - 1까지 2번밝고 온경우 i계단 까지는 연속 3번이되기 때문
  24. dp[i][1] = v[i] + dp[i - 1][0];
  25. }
  26.  
  27. printf("%d\n", max(dp[n - 1][0], dp[n - 1][1]));
  28. }
Add Comment
Please, Sign In to add comment