[백준] 계단오르기 in Java

📍 문제

DP 문제이다.

BFS로도 풀 수 있지만 bfs로 풀면 메모리초과로 실패가 뜬다..ㅠㅠ

📍 코드 설명

1. n번째 계단을 오르는 방법은 두가지이다
   1. n-1번째 -> n번째로 오르기 (연속 2계단)
   2. n-2번째 -> n번째로 오르기 (연속 1계단)
2. dp[stairsNum + 1][2] 를 두어서 dp[n][1] -> n-2, n으로 올라온 값 / dp[n][2] -> n-1, n으로 올라온 값을 두어 최대 값을 구한다.
3. dp[n][1] = Math.max(dp[n-2][1], dp[n-2][2]) + stairs[n]
   1. 두칸 전에는 한칸 연속으로 와도되고, 두칸 연속으로 와도 되기 때문에 어떤 값이 최대인지 판단한다
4. dp[n][2] = dp[n-1][1] + staris[n]
   1. 두칸 연속에서는 반드시 1칸 연속으로 온 애만 올 수 있기 때문에 최대를 판별할 필요가 없다

📍 코드

✔️ 코드

import java.io.*;
import java.util.*;

public class Main {
	static int[] stairs;
	static int[][] dp;
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int stairsNum = Integer.parseInt(br.readLine());
		
		stairs = new int[stairsNum+1];
		dp = new int[stairsNum+1][3]; //1 : i포함 연속 1칸  2 : i포함 연속 2칸
		for(int i = 1; i <= stairsNum; i++) {
			stairs[i] = Integer.parseInt(br.readLine());
		}
		
		//stairs가 0, 1, 2일때 index 에러 주의
		if(stairsNum >= 1) {
			dp[1][1] = stairs[1];
			dp[1][2] = stairs[1];
		}
		
		if(stairsNum >= 2) {
			dp[2][1] = stairs[2];
			dp[2][2] = stairs[1] + stairs[2];
		}
		
		for(int i = 3; i <= stairsNum; i++) {
			//i-2 -> i 밟아서 올라온 경우 (i-2에서 최대 점수로 올라와야함)
			dp[i][1] = Math.max(dp[i-2][1], dp[i-2][2]) + stairs[i];
			
			//i-1 -> i 밟아서 연속 2계단 밟아서 올라온 경우
			dp[i][2] = dp[i-1][1] + stairs[i];
		}
		
		//어떤 값이 최대인지 판단
		int answer = Math.max(dp[stairsNum][1], dp[stairsNum][2]);
		System.out.println(answer);	
	}
}

 

📍 틀린이유

솔직히 bfs로 풀어도 맞게해줘야하는거아닝감?

 

📍 기억할 것

n-2, n-1 -> n을 구할 수 있는 경우 dp로 푸는게 가장 빠른 방법이다!!