[백준-자바] N_2579 계단 오르기

0woy·2024년 1월 5일

DP 백준

코딩테스트

목록 보기

4/40

📜 문제

중요 조건

연속으로 3계단을 밟지 않아야 함
마지막 계단은 무조건 밟아야 함

N번째 계단을 밟는 방법?
1. n-3 → n-1 → n
2. n-2 → n

위의 두 가지 경우만 존재하므로 점화식을 세우면
i번째 계단을 밟을 때 최고 점수(이하 scores[i]):
scores[i] = Math.max(scores[i-3]+stairs[i-1],scores[i-2])+stairs[i]

✍ 부분 코드 설명

   public static void main(String [] args) throws IOException {
        BufferedReader br = 
        	new BufferedReader(new InputStreamReader(System.in));
        
        int count = Integer.parseInt(br.readLine());

        int [] stairs = new int[count+1]; // 각 계단의 점수 
        int [] scores = new int[count+1]; // 현 계단까지 최고 점수

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

count 변수에 계단의 개수를 입력 받고, stairs와 scores 배열을 선언한다.

데이터 입력 && 최고점 찾기

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

scores[1] = stairs[1];

for(int i=2;i<=count;i++){
	if(i==2)
		scores[2] = stairs[1]+stairs[2];
	else if(i==3)
    	scores[3] = Math.max(stairs[1],stairs[2])+stairs[3];
	else
    	scores[i] =  Math.max(scores[i-3]+stairs[i-1],scores[i-2])
       				+ stairs[i];
}

System.out.println(scores[count]);

🍳 전체 소스 코드


import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class N_2579 {
    public static void main(String [] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int count = Integer.parseInt(br.readLine());

        int [] stairs = new int[count+1]; // 각 계단의 점수 저장 배열
        int [] scores = new int[count+1];

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

        scores[1] = stairs[1];
        for(int i=2;i<=count;i++){
            if(i==2)
                scores[2] = stairs[1]+stairs[2];
            else if(i==3)
                scores[3] = Math.max(stairs[1],stairs[2])+stairs[3];
            else
                scores[i] =  Math.max(scores[i-3]+stairs[i-1],scores[i-2]) + stairs[i];
        }
        System.out.println(scores[count]);
    }
}

✨ 결과

🍰 오답 정리

A. 끝 계단부터 시작

틀린 결과를 도출한 코드는 마지막 계단을 무조건 밟아야 한다는 조건에 집중해서 끝 계단에서 출발하여 처음 계단으로 가는 방법을 선택하여 아래와 같이 작성했다.

public class N_2579 {
    public static void main(String [] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int total = 0; // 총 점수
        int count = Integer.parseInt(br.readLine());
        boolean check = false;  // 연속된 3계단 감지
        int [] stairs = new int[count]; // 각 계단의 점수 저장 배열

        for(int i=0;i<count;i++)
            stairs[i] = Integer.parseInt(br.readLine());

        total += stairs[count-1]; // 마지막 계단 필수
        int i;
        // 계단 오르기 시작
        for(i = count-1;i>=2;){
            if(!check && stairs[i-1] > stairs[i-2]){
                total+=stairs[i-1];
                i=i-1;
                check = true;
            }
            else{
                total+=stairs[i-2];
                i=i-2;
                check=false;
            }
        }
        if(!check) {
            switch (i) {
                case 1:
                    total += stairs[0];
                    break;
                case 2:
                    total += stairs[0]<stairs[1]?stairs[1]:stairs[0];
                    break;
            }
        }
        System.out.println(total);
    }
}

n-1과 n-2의 점수를 비교하여 더 큰 쪽으로 이동한다.

n-1의 계단으로 이동한 경우는, 다시 n-1번째 계단으로 이동할 수 없으므로 check 변수를 사용해 연속으로 3계단을 오르지 못하도록 한다.

위 코드는 6, [40, 40, 20, 1, 20, 5] 케이스가 반례를 나타냈다.

작성한 코드의 결과값은 5+20+20+40 = 85 가 나오지만,
답은 40+40+1+5 = 86이므로 다른 방법을 생각해야했다.

B. 인덱스 범위 초과 런타임 에러

런타임 에러 결과를 도출한 코드이다. 정답 코드에서 2, 3번째 값을 저장하는 코드를 for문 전에 작성했더니 발생했다.

scores[1] = stairs[1];
scores[2] = stairs[1]+stairs[2];
scores[3] = Math.max(stairs[1],stairs[2])+stairs[3];

for(int i=4;i<=count;i++)
		scores[i] =  Math.max(scores[i-3]+stairs[i-1],scores[i-2]) + stairs[i];