반응형
2579번: 계단 오르기
계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. <그림 1>과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점
www.acmicpc.net
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 | #include <iostream> #include <algorithm> using namespace std; int arr[301]; int dp[301]; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); int n; cin >> n; for (int i = 1; i <= n; i++) cin >> arr[i]; dp[0] = 0; dp[1] = arr[1]; dp[2] = arr[1] + arr[2]; for (int i = 3; i <= n; i++) dp[i] = max(arr[i - 1] + dp[i - 3], dp[i - 2]) + arr[i]; cout << dp[n]; } | cs |
반응형