2579번 - 계단 오르기
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]); }
}
for(int i=4;i<=numStairs;i++){dp[i] = stairs[i] + Math.max(dp[i-2], dp[i-3]+stairs[i-1]);}
이 부분에서 계단을 세번 오르는 경우에 대해 걸러주지 못하지 않나요?
댓글을 작성하려면 로그인해야 합니다.
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)) 으로 하였습니다.