import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.math.BigInteger;
import java.util.Scanner;
public class Main {
public static int[][] cache;
public static int input;
public static int[] list;
public static int min;
public static void main(String[] args) throws IOException {
// TODO Auto-generated method stub
Scanner sc = new Scanner(System.in);
BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
input = sc.nextInt();
list = new int[input+1];
for(int i = 1 ; i < input+1; i++){
list[i] = sc.nextInt();
}
cache = new int[input+1][3];
for(int i = 0; i < input+1; i++){
for(int j = 0 ; j < 3; j++){
cache[i][j] = -1;
}
}
StringBuffer sb = new StringBuffer();
System.out.println(dp(0,0,sb));
}
public static int dp(int n,int before,StringBuffer sb){
sb.append(n+"->");
int max = 0 ;
int originbefore = before;
//기저사례
if((n == input+1)|| (n == input+2)){
return 0;
}
if(cache[n][before] != -1){
return cache[n][before];
}
if(before < 2) {//한계단 올랐을때 한계단 또는 2계단을 오른다.
max = Math.max(max, list[n] + dp(n + 1, ++before,new StringBuffer(sb.toString())));
max = Math.max(max, list[n] + dp(n + 2,1,new StringBuffer(sb.toString())));
}else{ //이전에 오른 계단의 횟수가2회이면 연속이므로 2계단을 뛰어야한다.
before = 1;
max = Math.max(max, list[n] + dp(n + 2,before,new StringBuffer(sb.toString())));
}
//System.out.println(sb);
return cache[n][originbefore] = max;
// return max;
}
}
no20bhkim 7년 전
아래는 제가 만든 코드인데요
질문에 나온 테스트케이스는 다 통과하는거 같은데 결과는 틀렸다고 하네요.
StringBuffer sb = new StringBuffer(); System.out.println(dp(0,0,sb)); } public static int dp(int n,int before,StringBuffer sb){ sb.append(n+"->"); int max = 0 ; int originbefore = before; //기저사례 if((n == input+1)|| (n == input+2)){ return 0; } if(cache[n][before] != -1){ return cache[n][before]; }