백준 2579 - Java

import java.util.Scanner;

public class BJ2579 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n=sc.nextInt();
        int[] stairs = new int[301];
        int[] score = new int[301];
        //입력
        for(int i=1;i<=n;i++){
            stairs[i]=sc.nextInt();
        }
        score[1] = stairs[1];
        if (n >= 2) {
            score[2] = stairs[1] + stairs[2];
        }
        if (n >= 3) {
            score[3] = Math.max(stairs[1] + stairs[3], stairs[2] + stairs[3]);
        }

        for(int i=4;i<=n;i++){
            score[i] = Math.max(score[i - 2] + stairs[i], score[i - 3] + stairs[i - 1] + stairs[i]);
        }
        System.out.println(score[n]);
    }
}

 

 

 

동적 계획법을 사용하여 문제를 풀었다.  자세한 설명은 지피티로 대체하였다. 

동작 원리 설명

1. DP 배열과 점수 정의:
   • score[i]: iii번째 계단에 도달했을 때 얻을 수 있는 최대 점수.
   • stairs[i]: iii번째 계단에 적혀 있는 점수.
2. 점수 계산식:
   • Math.max(...)를 사용하여 두 가지 가능한 경우 중 더 큰 점수를 선택합니다.

두 가지 경우의 설명

• 첫 번째 경우: score[i - 2] + stairs[i]
  • 의미: i−2i-2i−2번째 계단에서 1단계 올라오는 경우입니다.
  • 설명:
    • 이전에 i−2i-2i−2번째 계단에 도달했을 때의 최대 점수인 score[i - 2]를 가져옵니다.
    • 그리고 iii번째 계단의 점수인 stairs[i]를 더합니다.
    • 따라서 이 경우는 i−2i-2i−2에서 한 단계 올라가는 것이므로 연속된 3개 계단을 밟지 않는 조건을 만족합니다.
• 두 번째 경우: score[i - 3] + stairs[i - 1] + stairs[i]
  • 의미: i−3i-3i−3번째 계단에서 2단계 올라오는 경우입니다.
  • 설명:
    • 이전에 i−3i-3i−3번째 계단에 도달했을 때의 최대 점수인 score[i - 3]를 가져옵니다.
    • 그리고 i−1i-1i−1번째 계단과 iii번째 계단의 점수를 각각 더합니다: stairs[i - 1]와 stairs[i].
    • 이 경우는 i−1i-1i−1과 iii번 계단을 밟는 것이므로, 3개의 연속된 계단을 밟지 않도록 하는 규칙을 만족합니다.

최종 점수 계산

• 두 경우에서 계산한 점수를 Math.max로 비교하여 더 큰 점수를 선택합니다.
• 이렇게 선택된 값이 score[i]에 저장됩니다.

예시

가령, 계단의 점수가 다음과 같다고 가정해 봅시다:

• stairs[1] = 10
• stairs[2] = 20
• stairs[3] = 30
• stairs[4] = 40
• stairs[5] = 50

이 경우, i=4i = 4i=4일 때:

• 첫 번째 경우:
  • score[4] = score[2] + stairs[4] = (10 + 20) + 40 = 70
• 두 번째 경우:
  • score[4] = score[1] + stairs[3] + stairs[4] = 10 + 30 + 40 = 80

최종적으로:

• score[4]는 Math.max(70, 80)이 되어 80이 저장됩니다.