[BOJ/2579] 계단 오르기

(공감과 댓글 하나는 글쓴이에게 큰 힘이 됩니다.)

 

문제 링크

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

 

사용 알고리즘

- DP

 

풀이

- d[i] = i번째 계단에 올라갔을 때의 최대 점수

- d[i] = max(d[i - 2] + a[i], d[i - 3] + a[i - 1] + a[i])

→ 1개 연속 : i - 2번째 계단은 밟고, i - 1번째 계단은 밟지 않아야 됨

→ 2개 연속 : i - 3번째 계단은 밟고, i - 2번째 계단은 밟지 않고, i - 1번째 계단은 밟아야 됨

 

소스 코드

- https://github.com/moomini/algorithm/blob/master/boj/2579.cpp

#include <cstdio> #include <algorithm>   using namespace std;   int d[303]; int a[303];   int main(void) {     int n; scanf("%d", &n);     int ans = -1;     for (int i = 1; i <= n; ++i) {         scanf("%d", &a[i]);         if (i == 1) d[i] = a[i];         else if (i == 2) d[i] = a[i] + a[i - 1];         else d[i] = max(d[i - 2] + a[i], d[i - 3] + a[i - 1] + a[i]);     }     printf("%d\n", d[n]);     return 0; } Colored by Color Scripter

cs