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

Problem

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

Approach & Logic

[문제 규칙]

1. 계단은 한 번에 한 계단씩 또는 두 계단씩 오를 수 있다. 즉, 한 계단을 밟으면서 이어서 다음 계단이나, 다음 다음 계단으로 오를 수 있다.
2. 연속된 세 개의 계단을 모두 밟아서는 안 된다. 단, 시작점은 계단에 포함되지 않는다.
3. 마지막 도착 계단은 반드시 밟아야 한다.

마지막 계단(n)은 반드시 밟아야 하므로 마지막 계단(n)을 밟기 전에 두가지의 경우의 수가 존재한다.
1) n-3계단을 밟고 두칸을 올라 n-1계단을 밟고 한칸을 올라 마지막 계단n을 밟는 방법
2) n-2계단을 밟고 두칸을 올라 마지막 계단n을 밟는 방법

=> '위의 경우 2가지 중 큰 값' + '현재 계단의 값'이 해당 칸의 최대값이 된다
==> dp[i] = Math.max(dp[n-3] + stair[n-1], dp[n-2]) + stair[n]

사소한 실수

처음에 다음과 같이 1, 2, 3번 계단은 값을 직접 지정하는 방법으로 코드를 작성했지만

dp[1] = stair[1];
dp[2] = stair[1] + stair[2];
dp[3] = Math.max(stair[1], stair[2]) + stair[3];

해당 배열을 초기화할 때 사용자로부터 입력받은 n값으로 초기화하는 방법으로 코드를 작성해서 런타임 에러 (ArrayIndexOutOfBounds) 가 났다..

int n = Integer.parseInt(br.readLine());
int[] stair = new int[n+1];
int[] dp = new int[n+1];

런타임 에러 이유는 n값이 1일때는 stair[3]과 dp[3]은 애초에 선언되지 않았는데 dp[3]을 계산하려고 하고 있기 때문이다.

따라서,

해결방안 1)
문제에서 계단의 개수는 300이하의 자연수라고 했으므로 stair 와 dp를 선언할때 배열크기를 301로 선언한다.

int[] stair = new int[301];
int[] dp = new int[301];

dp[1] = stair[1];
dp[2] = stair[1] + stair[2];
dp[3] = Math.max(stair[1], stair[2]) + stair[3];

해결방안 2)
사용자로부터 입력받은 n값으로 초기화하는 방법을 사용하고 싶다면 dp[1], dp[2], dp[3] 값을 계산하는 부분을 for문안에 if문으로 구현한다.

int n = Integer.parseInt(br.readLine());
int[] stair = new int[n+1];
int[] dp = new int[n+1];
        
for(int i=1; i<=n; i++) {
	if(i==1) 
    	dp[1] = stair[1];
    else if(i==2)
    	dp[2] = stair[1] + stair[2];
    else if(i==3)
    	dp[3] = Math.max(stair[1], stair[2]) + stair[3];
    else
    	dp[i] = Math.max(dp[i-3] + stair[i-1], dp[i-2]) + stair[i];
            
}

---

Code

해결방안 1

import java.io.*;

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[] stair = new int[301];
        int[] dp = new int[301];
        
        for(int i=1; i<=n; i++) {
            stair[i] = Integer.parseInt(br.readLine());
        }
        
        dp[1] = stair[1];
        dp[2] = stair[1] + stair[2];
        dp[3] = Math.max(stair[1], stair[2]) + stair[3];

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

        System.out.println(dp[n]);
    }
}

해결방안 2

import java.io.*;

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[] stair = new int[n+1];
        int[] dp = new int[n+1];

        for(int i=1; i<=n; i++) {
            stair[i] = Integer.parseInt(br.readLine());
        }
    
        for(int i=1; i<=n; i++) {
            if(i==1) 
                dp[1] = stair[1];
            else if(i==2)
                dp[2] = stair[1] + stair[2];
            else if(i==3)
                dp[3] = Math.max(stair[1], stair[2]) + stair[3];
            else
                dp[i] = Math.max(dp[i-3] + stair[i-1], dp[i-2]) + stair[i];
        }

        System.out.println(dp[n]);
    }
}

+참고로 성능은 해결방안2이 진짜 조금 더 좋았다..!