[백준 2579, Java] 계단 오르기

문제

www.acmicpc.net/problem/2579

2579번: 계단 오르기

comment

 컨디션에 상관 없이 문제를 풀었음 좋겠다. 예외케이스을 생각하지 못한다거나, 풀이가 생각났다고 바로 코딩하려는 습관이나, 풀때마다 풀이가 달라지지 않도록 더 연습

 

 

 

풀이

- 연속된 세 개의 계단을 모두 밟으면 안된다는 조건이 없다면 점화식 f(n) 을 n번째 계단을 오를 때의 최대 점수 라고 정의하는 경우 f(n) = max( f(n-1), f(n-2) ) + score[n] 이 된다.  

 

실수한 것

- "연속된 세 개의 계단을 모두 밟아서는 안 된다 " 를 1칸 -> 1칸 -> 1칸 이렇게 이동하면 안되는 것이라 생각. 그래서

f(n,1) = Max( f(n-2,2)+score[n-1], f(n-1, 2) ) + score[n] 이라고 했다. 

 

- 초기화! 맨 처음에는 

    public static long getMaxScore(int N){
        memo[1][1] = scores[1];
        memo[2][1] = scores[1] + scores[2];
        memo[2][2] = scores[2];

        for(int index = 3; index<=N; index++){

            memo[index][1] = memo[index-1][2] + scores[index];
            memo[index][2] = Math.max(memo[index-2][1], memo[index-2][2]) + scores[index];
        }

        return Math.max(memo[N][1], memo[N][2]);
    }

이렇게 초기화를 했다. 이 것의 문제는 N=1 일때 배열의 크기가 2가 되는데, 이때 인덱스 2에는 접근할 수 없어 런타임 에러가 난다

 

코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

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

        N = Integer.parseInt(br.readLine().trim());
        scores = new int[N+1];
        memo = new long[N+1][3];
        for(int index = 1 ; index<=N; index++){
            scores[index] = Integer.parseInt(br.readLine());
        }

        long result = getMaxScore(N);
        bw.write(String.valueOf(result));
        bw.flush();

        br.close();
        bw.close();

    }
    public static long getMaxScore(int N){
        for(int index = 1; index<=N; index++){
            if(index == 1){
                memo[1][1] = scores[1];
            }
            else if( index== 2){
                memo[2][1] = scores[1] + scores[2];
                memo[2][2] = scores[2];
            }
            else{
                memo[index][1] = memo[index-1][2] + scores[index];
                memo[index][2] = Math.max(memo[index-2][1], memo[index-2][2]) + scores[index];

            }
        }

        return Math.max(memo[N][1], memo[N][2]);
    }
}