백준 2579번 계단 오르기

✍️ 문제 풀이

---

• 접근 방법
  • DP(Dynamic Progmamming)
  • Bottom-Up

1. 테이블 정의하기
   D[i][j] = 현재까지 j개의 계단을 연속해서 밟고 i번째 계단까지 올라섰을 때 점수 합의 최댓값, 단 i번째 계단은 반드시 밟아야 함

2. 점화식 찾기
   

3. 초기값 세팅
   

참고 자료
https://blog.encrypted.gg/974

💻 java 구현 코드

package ch10_DynamicProgramming;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Scanner;

public class p2579 {

	public static void main(String[] args) throws IOException {
	
		Scanner scanner = new Scanner(System.in);
		
		int N = scanner.nextInt();
		
		int[] score = new int[N + 1];  // 각 계단에서 얻을 수 있는 점수
		int[][] dp = new int[N + 1][3];  // DP테이블 (각 계단까지 올라갔을 때 얻을 수 있는 점수의 최댓값)
		
		// score 배열 값 세팅
		for (int i = 1; i <= N; i++) {
			score[i] = scanner.nextInt();
		}
		
		// 예외 처리
		if (N == 1) {
			System.out.println(score[1]);
			return;
		}
		
		// 초기값 세팅
		dp[1][1] = score[1]; dp[1][2] = 0;
		dp[2][1] = score[2]; dp[2][2] = dp[1][1] + score[2];
		
		// DP테이블 값 세팅
		for (int i = 3; i <= N; i++) {
			dp[i][1] = Math.max(dp[i - 2][1], dp[i - 2][2]) + score[i];
			dp[i][2] = dp[i - 1][1] + score[i];
		}
		
		System.out.println(Math.max(dp[N][1], dp[N][2]));
	}
}

💡 문제 해결

❗️ 런타임 에러

package ch10_DynamicProgramming;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Scanner;

public class p2579 {

	public static void main(String[] args) throws IOException {
	
		Scanner scanner = new Scanner(System.in);
		
		int N = scanner.nextInt();
		
		int[] score = new int[N + 1];  // 각 계단에서 얻을 수 있는 점수
		int[][] dp = new int[N + 1][3];  // DP테이블 (각 계단까지 올라갔을 때 얻을 수 있는 점수의 최댓값)
		
		// score 배열 값 세팅
		for (int i = 1; i <= N; i++) {
			score[i] = scanner.nextInt();
		}
		
		// 초기값 세팅
		dp[1][1] = score[1]; dp[1][2] = 0;
		dp[2][1] = score[2]; dp[2][2] = dp[1][1] + score[2];
		
		// DP테이블 값 세팅
		for (int i = 3; i <= N; i++) {
			dp[i][1] = Math.max(dp[i - 2][1], dp[i - 2][2]) + score[i];
			dp[i][2] = dp[i - 1][1] + score[i];
		}
		System.out.println(Math.max(dp[N][1], dp[N][2]));
	}
}

N의 값으로 1이 입력될 수 있는데, 이에 대한 예외처리 없이
dp[2][1] = score[2]; dp[2][2] = dp[1][1] + score[2]; 라인을 무조건 수행하도록 코드를 작성해서 런타임 에러가 발생하였다.

아래 코드를 추가해줌으로써 해당 에러를 해결하였다.

	// 예외 처리
		if (N == 1) {
			System.out.println(score[1]);
			return;
		}