lsm941010   6년 전

package study.problem.b2579;

import java.util.Scanner;

public class Main {

public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner sc = new Scanner(System.in);
int numStairs = sc.nextInt();

int stairs[] = new int[numStairs+1];
for(int i=1;i<=numStairs;i++)
stairs[i] = sc.nextInt();

int dp[] = new int[numStairs+1];

dp[0] = 0;
dp[1] = stairs[1];
dp[2] = stairs[1] + stairs[2];
dp[3] = stairs[3] + Math.max(dp[1], stairs[2]);

for(int i=4;i<=numStairs;i++){
dp[i] = stairs[i] + Math.max(dp[i-2], dp[i-3]+stairs[i-1]);
}

System.out.println(dp[numStairs]);
}

}

점화식은 f(i) = stairs(i) + Math.max(f(i-2), stairs(i-1)+f(i-3)) 으로 하였습니다.
코드를 아무리 고쳐봐도 9%에서 계속 틀리는데 무엇이 잘못됬는지 알려주시면 감사하겠습니다.

4rchive_7   6년 전

for(int i=4;i<=numStairs;i++){
dp[i] = stairs[i] + Math.max(dp[i-2], dp[i-3]+stairs[i-1]);
}

이 부분에서 계단을 세번 오르는 경우에 대해 걸러주지 못하지 않나요?

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