[백준 2579] - 계단오르기 - JAVA [DP]

안녕하세요 놀이방 사장입니다.

 

이번 포스팅은 백준 2579

"계단오르기" 입니다.

 

2579번: 계단 오르기

 

DP문제입니다.

점화식을 구해야하는데 점화식은 

이 조건을 보고 만들어야 합니다.

 

포스팅을 참조하다가 점화식을 제대로 설명해주는 그림이 있어 가지고 와봤습니다. (밑에 블로그에서 가지고 왔습니다.)

[백준] 2579번 : 계단 오르기 - JAVA [자바]

이 사진이 점화식을 그대로 설명해주는 이미지입니다.

n을 밟을 떄 경우의 수가 2가지가 있는 거죠

1. n 계단 전에 -3번째계단을 밟고 -1계단을 밟고 n번쨰 계단을 밟는 거죠

2. n-2번쨰 계단을 밟고 n번쨰 계단을 밟는다.

이걸 점화식으로 구현해주면

arr[i] = Math.max((arr[i-3]+stair[i-1]), arr[i-2]) + stair[i];

 

코드로 구현해보겠습니다.

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.IOException;

public class Main{
    static int[] arr = new int[301];  //점수
    static int[] stair = new int[301];  //계단에 부여되어있는 점수

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());

        for(int i=1; i<=n; i++){
            stair[i] = Integer.parseInt(br.readLine());
        }
        arr[1] = stair[1];
        arr[2] = stair[1] + stair[2];
        arr[3] = Math.max(stair[1], stair[2]) + stair[3];
        for(int i=4; i<= n; i++){
            arr[i] = Math.max((arr[i-3]+stair[i-1]), arr[i-2]) + stair[i];
        }
        System.out.println(arr[n]);
    }
}

 

문제랑 이미지를 생각해보시면 이해가 되실 거라고 생각합니다.

저도 저 이미지보고 이해를 했습니다.