2579 계단 오르기

import java.io.IOException;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.BufferedWriter;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;
public class main {
	static int[][] dp;
	static int N;
    static StringTokenizer st;
	public static void main(String[] args) throws IOException {
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    	
       	N = Integer.parseInt(br.readLine());
       	dp = new int[N+1][3]; //1, 2 : 전에 칸 개수 
       	
       	for(int i =1; i<=N; i++) {
       		dp[i][1] = Integer.parseInt(br.readLine());
       		dp[i][2]=dp[i][1];
       	}
       	
       	if(N==1) {
       		bw.write(dp[N][1]+" ");
        	bw.flush();
        	bw.close();
        	return;
       	}else if(N==2) {
       		bw.write((dp[1][1]+dp[N][1])+" ");
        	bw.flush();
        	bw.close();
       		return;
       	}
       	
       	dp[1][2]=0;
       	dp[2][1]+=dp[1][1];
       			
       	for(int i =3; i<N; i++) {
       		dp[i][1] += dp[i-1][2];
       	    dp[i][2] += Math.max(dp[i-2][1],dp[i-2][2]);
       	}
       	
   		bw.write(Math.max(dp[N-1][2],Math.max(dp[N-2][1],dp[N-2][2])) + dp[N][1]+" ");
    	bw.flush();
    	bw.close();
    }
}

 

예외처리가 살짝 지저분해 보이네 ㅎ ,,

풀고 나서 사람들 풀이 봤는데 아예 점수 배열을 따로,, 만들더라구요?

 

난,, 이차원 배열로 dp배열을 만들었다.. ㅎ

[1]에는 바로 직전에서 온 애들 [2]에는 전 전에서 온애들을 저장했다.

 

그래서 바로 전에서 온애는 연달아가 안되니까 [2]애들을 더해주고,

전전에서 온애는 다 올 수 있으니 [1],[2] 중에 큰 값 더해준다.

전 전에서서는 그 전에 한칸 올랐는지 두칸올랐는지 상관없으니 다 갈 수있으니깐~

 

그 식이

dp[i][1] += dp[i-1][2]

dp[i][2] += Math.max(dp[i-2][1], dp[i-2][2]

 

예엥~

 

---

새로 푼거

import java.io.IOException;
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
public class main {

	static int dp[];
	static int arr[];
	static int N;

	public static void main(String[] args) throws IOException{
    
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		N = Integer.parseInt(br.readLine());
		arr = new int[N+1];
		dp = new int[N+1];
		
		for(int i=1; i<=N; i++) {
			arr[i] = Integer.parseInt(br.readLine());	
		}
		
		if(N==1) {
			bw.write(arr[1]+"\n");
			bw.flush();
			bw.close();	
			return;
		}
		
		dp[1]= arr[1];
		dp[2]= arr[1] + arr[2];
		
		for(int i=3; i<=N; i++) {
			dp[i] = Math.max(dp[i-2]+arr[i],dp[i-3]+arr[i]+arr[i-1]);
		}
				
		bw.write(dp[N]+"\n");
		bw.flush();
		bw.close();	
    }
}

예엥