백준 2579 계단 오르기(Java)

https://www.acmicpc.net/problem/2579

2579번: 계단 오르기

---

 

해석 및 팁

 

---

 

이 문제에서 n번째 계단을 오르는 경우는 n-3을 밟고 n-1번 계단을 밟고 오는 경우와 n-2번을 밟고 오는 경우 2가지가 존재합니다. 먼저 계단의 점수 배열과 n번째 계단까지의 점수배열을 만들었을 때  score [n] = Math.max(score [n-3] + stair [n-1], score [n-2]) + stair [n]이라는 식이 만들어집니다. n번째까지의 점수의 값을 출력해 주면 됩니다.

 

---

 

Java 코드

 

---

import java.util.Scanner;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);

    int n = sc.nextInt();

    int[] stair = new int[n+1];
    int[] score = new int[n+1];
  
    for(int i = 1; i <= n; i++) {
      stair[i] = sc.nextInt();
    }

    score[0] = 0;
    score[1] = stair[1];

    if(n > 1) score[2] = stair[1] + stair[2];

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