[java] 백준 알고리즘 2579번 계단오르기 풀이소스

문제를 푸는데 조건을 잘 이해하는게 중요하다고 느끼는데,

세세한 조건을 착각하는 경우가 많다.

이번에도 첫번째 계단을 꼭 밟을 필요가 없지만, 

예시에서는 첫 번째 계단을 시작점과 동시에 밟아야한다고 혼자 착각해서

원리가 맞음에도 불구하고, 초기값으로 넣어줄 세번째 계단 때문에 

계속 틀렸다고 떴다. 첫번째 계단을 건너 뛰고 바로 갈 수도 있는 경우를 넣어줘야했는데 말이다...

아래부터 문제와 풀이!

조건은 총 세가지가 있다.

조건 세가지 모두 만족하려면,

마지막 계단의 점수는 더해주고, 두번째 칸 전(-2)의 계단에서 바로 마지막 계단을 밟든지,

세번째 칸 전(-3)의 계단에서 마지막 계단의 한 칸 전(-1)의 계단을 밟고 마지막 계단을 밟으면 된다.

이렇게 밟으면 계속해서 계단의 텀이 지속해서 2칸씩은 나오기 때문에 

2번째 조건인 세개의 계단을 연속해서 밟지 않을 수 있다. 

*소스

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
 
public class Baekjoon2579 {
    
    private static BufferedReader br;
    
    public static void main(String[] args) throws NumberFormatException, IOException{
        br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine()); // 입력하는 계단의 갯수
        
        int outputStairScore = maxStairScore(n); // 계단 점수 총합의 최대값
       
        System.out.println(outputStairScore);
        
    }
    
    private static int maxStairScore(int n) throws NumberFormatException, IOException{
        
         int[] eachScoreArray = new int[300]; // 계단의 개수가 300 이하의 자연수
            
         for(int i=0; i<n; i++){
             eachScoreArray[i] = Integer.parseInt(br.readLine()); // 계단 각각 가지고 있는 점수의 배열
         }
         
         int[] maxStairScoreArray = new int[300]; // 계단 점수 총합의 최대값이 모일 배열
         maxStairScoreArray[0] = eachScoreArray[0];
         maxStairScoreArray[1] = eachScoreArray[0] + eachScoreArray[1];
         
         /* 꼭 첫번째 계단을 밟을 필요는 없다. 시작선이 첫번째 계단은 꼭 밟아야하는 줄 알고 계속 실패했다 ㅠㅠ */
         maxStairScoreArray[2] = Math.max(eachScoreArray[0] + eachScoreArray[2], eachScoreArray[1] + eachScoreArray[2]);
         
         if(n>3){
             for(int j=3; j<n; j++){
                 
                /* 3칸 전 계단까지 총합의 최대값+마지막계단의 한 칸 전 계단 점수 합이 큰지, 두 칸 전 계단까지 총합의 최대값이 큰지 비교 */
                 if(maxStairScoreArray[j-3] + eachScoreArray[j-1] > maxStairScoreArray[j-2]){
                     
                     maxStairScoreArray[j] = eachScoreArray[j] + maxStairScoreArray[j-3] + eachScoreArray[j-1];  
                 }else{
                     maxStairScoreArray[j] = eachScoreArray[j] + maxStairScoreArray[j-2];
                 }
             }
         }
          
         return maxStairScoreArray[n-1];
    }
}