busyhuman   9달 전

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

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



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

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

busyhuman   9달 전

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

sang7   8달 전

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달 전

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

늦었지만 감사합니다

busyhuman   8달 전

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

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