[백준] 2579번: 계단 오르기

백준 2579번: 계단 오르기

1. 문제 설명

2. 문제 풀이

• 주의 사항
  1. 배열의 0번째 값은 계단이 아닌 시작 위치
  2. 입력받은 계단의 수가 1인 경우 예외 처리
  3. 재귀호출시 n-2 와 n-3만 재귀호출 하고, n-1은 재귀호출을 하지 않음.
     => 연속해서 3개의 계단을 밟는 것은 불가능하기 때문

     //n-2번을 밟은 경우: step(n-2)
     //n-3을 밟고 n-1번 계단을 밟고 오는 경우: step(n-3)+score[n-1]
     dp[n]=Math.max(step(n-2),step(n-3)+score[n-1])+score[n];

코드

import java.util.*;
public class No_2579 {

	static int [] score;
	static int [] dp;
	public static void main(String[] args) {

		Scanner sc = new Scanner(System.in);
		
		int N=sc.nextInt();
		
 		//N+1인 이유는 배열 0번째 index를 시작점이라고 가정
		score=new int[N+1];
		dp=new int[N+1];
		
		for(int i=1;i<N+1;i++) {
			score[i]=sc.nextInt();
		}
		
                              
		dp[0]=score[0];
		dp[1]=score[1];
		
		//입력받은 계단 개수(N)가 1인 경우
		if(N>=2) {
			dp[2]=score[1]+score[2];
		}
		
		System.out.println(step(N));
	}
	
	public static int step(int n) {
		
		if(n>=3){
			if(dp[n]==0)
               //n-2번을 밟은 경우: step(n-2)
               //n-3을 밟고 n-1번 계단을 밟고 오는 경우: step(n-3)+score[n-1]
				dp[n]=Math.max(step(n-2),step(n-3)+score[n-1])+score[n];
		}
		return dp[n];
	}

}

실행 결과