[백준] 2579 - 계단 오르기 JAVA

Solved.ac Class 완전정복 프로젝트

Class : 3 ~ 3 ++

 

---

링크

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

2579번: 계단 오르기

문제

계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. <그림 1>과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점수를 얻게 된다.

<그림 1>

 

 예를 들어 <그림 2>와 같이 시작점에서부터 첫 번째, 두 번째, 네 번째, 여섯 번째 계단을 밟아 도착점에 도달하면 총점수는 10 + 20 + 25 + 20 = 75점이 된다.

 

<그림 2>

 계단 오르는 데는 다음과 같은 규칙이 있다.

 

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

 

따라서 첫 번째 계단을 밟고 이어 두 번째 계단이나, 세 번째 계단으로 오를 수 있다. 하지만, 첫 번째 계단을 밟고 이어 네 번째 계단으로 올라가거나, 첫 번째, 두 번째, 세 번째 계단을 연속해서 모두 밟을 수는 없다.

각 계단에 쓰여 있는 점수가 주어질 때 이 게임에서 얻을 수 있는 총점수의 최댓값을 구하는 프로그램을 작성하시오.

접근방법

 3 연속으로 계단을 밟지 않고 목적지까지 가는 최대의 값을 도출하는 문제이다. 분할 정복을 통한 DP문제이다. 이전에 어떤 계단을 밟았는지에 따라 현재 밟을 수 있는 계단이 정해지지만, 해당 상황은 각 계단마다 반복되기 때문이다. (이 문제를 보고 DP문제라고 판단하지 못했다면, 개념을 다시 한번 공부하는 것이 우선이어야 한다.) DP문제임을 인지하고 풀이로 들어가자.

 

풀이

  DP [N]은 N번째 계단까지 올라갔을 때의 최댓값이라고 정의할 때, N번째 계단을 반드시 밟는 경우는 다음과 같다.

 

1. 현재 위치가 연속된 계단 중 첫 번째 계단이다.(전전 계단을 밟고 두 계단을 오른 케이스)
2. 현재 위치가 연속된 계단 중 두 번째 계단이다.(전 계단을 밟고 한 계단을 오른 케이스)

 

그림으로 표현하면 다음과 같다. 해당 그림에서 노란색 막대는 마지막, 화살표는 밟는 계단의 경우이다.

 

 

 첫 번째 케이스의 경우, N-2칸 까지 계산된 결과에 현재 칸인 N의 값을 더하기만 하면 문제가 없다. 두 계단을 오른 첫 번째 계단인 상태이므로, 이전까지 계산된 결과를 신경 쓸 필요가 없다. 즉 DP [N-2]까지의 결과에 현재 계단 값만 더해주면 된다.

 

 두 번째 케이스의 경우, N-1칸을 밟고 현재를 연속된 두번째 계단으로 밟아야 하는 상황이다. 이 경우에는 DP [N-1]값을 사용할 수 없다. DP [N-1] 값이 연속된 두 계단을 밟은 상태인지, 아닌지 를 판단할 수 없다. 따라서 N-1번째 계단과 N번째 계단이 연속된 계단이 될 수 있도록, 그 이전으로 돌아가야 한다.  두 계단이 연속되려면, N-2 칸은 반드시 뛰어넘어야 하므로, DP [N-3]의 값을 이용환다.   

 

두 케이스 중 큰 값을 선택하며 나간다면, 최댓값을 도출할 수 있다.

 

실패 원인

 나는 DP를 이용할 때 최대 연속 계단의 수에 집착했다. 계단을 3칸식 쪼개서 구현했다. 그러다 보니, 많은 경우의 수를 모두 생각해야 했고, 또한 계단이 4나 5처럼 나머지가 생기는 경우를 따로 처리해야 했다.

 

코드

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

public class Main {

    public static void main(String[] args) throws IOException {
        Main test = new Main();
    }

    public Main() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int cnt = Integer.parseInt(br.readLine());

        int[] datas = new int[cnt+1];
        for (int i = 1; i <= cnt; i++) {
            datas[i] = Integer.parseInt(br.readLine());
        }

        System.out.println(solution(datas,cnt));
    }

    private int solution(int[] datas,int cnt) {

        int[] DP = new int[datas.length];

        if(cnt<3){
            for (int i = 1 ; i <= cnt;i++){
                DP[i] = datas[i]+DP[i-1];
            }
            return DP[cnt];
        }


        DP[1] = datas[1];
        DP[2] = datas[2]+DP[1];
        for (int i =3 ; i <= cnt ; i++){
            DP[i] = datas[i]+Math.max(datas[i-1] + DP[i-3],DP[i-2]);
            //System.out.println("DP ["+i +"]  : "+DP[i]);
        }
        
        return DP[cnt];
    }
}

결과

 

 

 연속적인 분할 정복에 대해 아직 구현하는 연습이 많이 필요하다고 느꼈다. 보자마자 DP문제임을 인식했지만, 3배 수로 쪼개서 구현을 하려고 했다. 이 문제를 재귀로 풀려했다면, 연속성을 찾기 위해 더 노력했을 것이다. 가급적 재귀를 피하고, 메모이제이션을 통해 DP를 구현하려고 노력하다 보니, 이런 부분을 너무 간과했던 것 같다.  이번 문제의 경우 재귀로 먼저 접근/구현하고, 메모이제이션으로 바꿔 풀었다면, 더 공부가 되었을 텐데, 욕심부리다가 결국 틀린 것이 많이 아쉬운 문제였다.

 

---

포스팅에 문제가 있거나, 설명이 잘못된 부분 지적 환영합니다.

더 나은 퀄리티의 콘텐츠를 제공할 수 있도록 노력하겠습니다.

읽어주셔서 감사합니다.