[백준 2579] 계단 오르기 (JAVA)

백준 2579번 문제 - 계단 오르기

2579번: 계단 오르기

---

문제 분석

 

•  

 

• 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다.
• 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점수를 얻게 된다.
• 계단 오르는 규칙
  • 계단은 한 번에 한 계단씩 또는 두 계단씩 오를 수 있다. 즉, 한 계단을 밟으면서 이어서 다음 계단이나, 다음 다음 계단으로 오를 수 있다.
  • 연속된 세 개의 계단을 모두 밟아서는 안 된다. 단, 시작점은 계단에 포함되지 않는다.
  • 마지막 도착 계단은 반드시 밟아야 한다.

---

해결 포인트

 

• 방법 1 : 재귀함수 사용 → 실패 ! 시간 초과 !
  • 계단 위치와 연속 계단 갯수를 재귀함수 호출시 같이 전달하는 재귀함수 구현
  • Math.max(stairsSum(index + 1, count+1), stairsSum(index + 2, 1)) + stairs[index]; 로 구하기
  • 연속 계단 갯수가 3 이상이면 음수 반환
• 방법 2 : DP 사용 (힌트 확인) → 실패 ! 3번째 계단 dp가 잘못된 것 같다.
  • dp[0], dp[1], dp[2]는 알고 있는 값으로 설정 후, dp[3]부터 계산
    - dp[0] (1번째 계단) : 1번째 계단 점수 | dp[1] : 1번째 계단 점수 + 2번째 계단 점수 | dp[2] : Math.max(2번째 계단 점수 , 1번째 계단 점수) + 3번째 계단 점수
  • 계산 방법
    : 연속 3칸이 안되므로 바로 전에 계단을 뛴 경우 (dp[n-2]), 2계단 전 계단을 뛴 경우 (dp[n-3] + dp[n-1]) 중에 큰 값에 현재 계단 점수 더하기
• 방법 3 : DP 사용 → 성공 !
  • dp[0], dp[1]는 알고 있는 값으로 설정 후, 계단 수가 2보다 클 경우 2도 설정 후, dp[3]부터 계산
    - dp[0](계단 오르기 전) : 0 | dp[1](1번째 계단) : 1번째 계단 점수 | dp[2](2번째 계단) : 1번째 계단 점수 + 2번째 계단 점수
  • 3번째 계단부터 계산 방법
    : dp[i] = Math.max(dp[i-3] + stairs[i-1], dp[i-2]) + 현재 계단 점수

---

코드

 

import java.io.*;

public class Main {
    public static int N;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        N = Integer.parseInt(br.readLine());

        int [] stairs = new int[N+1];
        for (int i = 1; i <= N; i++) {
            stairs[i] = Integer.parseInt(br.readLine());
        }

        int [] dp = new int[N+1];
        dp[0] = 0;
        dp[1] = stairs[1];
        if(N >= 2) {
            dp[2] = stairs[1] + stairs[2];
        }
        for (int i = 3; i <= N; i++) {
            dp[i] = Math.max(dp[i-3] + stairs[i-1], dp[i-2]) + stairs[i];
        }

        bw.write(dp[N] + "\n");

        bw.flush();
        bw.close();
    }

}