글 읽기 - 계단오르기 문제

busyhuman 8년 전 2

계단을 내려가는 식으로, 맨 위 계단을 무조건 밟고 내려오는 식으로 만들었습니다.

볼수록 감이 안잡힙니다..

테스트케이스------------------------------------------------------------------------------------

7
10 10 15 10 20 15 10
60

7
10 10 15 10 20 15 20
70

7
1 10 15 10 20 15 20
65

7
10 12 15 100 20 15 10
152

7
10 10 15 20 10 15 10
70

7
10 12 15 100 20 25 10

160

#include <iostream>
using namespace std;
int arr[305], dp[305];
int max(int x, int y){
	if (x > y)
		return x;
	return y;
}
int main(){
	int i, n,m;
	cin >> n;
	for (i = n; i > 0; i--)
		cin >> arr[i];

	dp[0] = arr[0] = 0;
	dp[1] = arr[1];
	dp[2] = arr[1] + arr[2];
	dp[3] = arr[1] + arr[3];

	for (i = 4; i <= n; i++){
		dp[i] = max(arr[i] + dp[i - 2], arr[i] + arr[i - 1] + dp[i - 3]);
		cout << "dp[" << i << "] = " << dp[i] << "\n";
	}
	cout << max(dp[n], dp[n - 1]);
	return 0;
}

busyhuman 8년 전 1

..................

sang7 8년 전 1

1칸 짜리 계단 이라면 계단 하나를 밟아야 최고죠.

2칸 짜리 계단 이라면 2계단을 모두 밟아야 합니다.

3칸 이면 모두 밟을 수 없으나 3번째 계단은 꼭 밟고 1~2칸중 큰 계단 하나를 밟아야 할 것입니다.

dp[0] = arr[0];

dp[1] = arr[0] + arr[1];

dp[2] = Max(arr[0] + arr[1]) + arr[2];

이고 4번 째 계단도 생각해보시면 점화식을 만드실 수 있을 거 같네요.

busyhuman 8년 전 1

22번째 줄을 지웠더니 해결되었습니다

늦었지만 감사합니다

busyhuman 8년 전 1

이게 내려오는 식으로 만들어서 3번째 계단을 밟을 때 첫번째 계단을 무조건 밟는 식으로 만들었습니다.

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

계단오르기 문제

busyhuman 8년 전 2

busyhuman 8년 전 1

sang7 8년 전 1

busyhuman 8년 전 1

busyhuman 8년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말