[Java] 백준 - 2579번: 계단 오르기

5월 18일(목) - 동적 계획법 1 (2579번)

2579번: 계단 오르기

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

 

문제점

// 수정 전
	dp[0] = 0;
        dp[1] = stairs[1];
        dp[2] = stairs[1] + stairs[2];
        for(int i=3; i<=N; i++)
        {
            dp[i] = stairs[i] + Math.max(dp[i-2], stairs[i-1] + dp[i-3]);
        }
        
        
// 수정 후
        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] = stairs[i] + Math.max(dp[i-2], stairs[i-1] + dp[i-3]);
        }

1. 위와같이 제출했더니 런타임 에러(ArrayindexOutOfBounds) 가 발생

풀이 - 1)

-> 배열 stairs와 dp의 크기를 N+1로 설정했던 것을 301로 수정

 

풀이 - 2)

-> 분기점을 계단의 수가 3개 이상인 경우부터 for문을 돌리던 것에서 2개 이상인 경우로 변경

-> 계단의 수가 2개 이상인 경우부터 if문을 추가하여 dp[2]값을 계산해주면서 해결

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

 

풀이 - 1

(C언어 풀이 활용)

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[301];
        int[] dp = new int[301];

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

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

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

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

 

풀이 - 2

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

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

        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] = stairs[i] + Math.max(dp[i-2], stairs[i-1] + dp[i-3]);
        }

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

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ