백준 2579 계단 오르기 자바

계단 오르기 문제 보러가기

2579번: 계단 오르기

문제 설명

자바 코드

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

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int[] stairs = new int[n + 1];
        int[] maxScore = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            stairs[i] = Integer.parseInt(br.readLine());
        }
        if (n >= 1)
            maxScore[1] = stairs[1];
        if (n >= 2)
            maxScore[2] = stairs[1] + stairs[2];
        if (n >= 3)
            maxScore[3] = Integer.max(stairs[1] + stairs[3], stairs[2] + stairs[3]);
        for (int i = 4; i <= n; i++) {
            maxScore[i] = Integer.max(maxScore[i - 3] + stairs[i - 1] + stairs[i], maxScore[i - 2] + stairs[i]);
        }
        System.out.print(maxScore[n]);
    }
}

문제 풀이

이 문제는 동적계획법을 이용하여 풀었습니다.

동적계획법은 각 결과값을 저장하여 앞서 저장한 결과값을 이용하여 다음 결과값을 도출하는 방법입니다.

해당 문제는 maxScore[i] = Integer.max(maxScore[i - 3] + stairs[i - 1] + stairs[i], maxScore[i - 2] + stairs[i]) 이부분이 핵심인데

예를 들어 4개의 계단이라면 4단계의 최대값 = 1+2+4 or 1+3+4 인데 더 나아가서 -> 1의결과값+2+4 or 2의결과값+4가 됩니다.