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

이 글은 읽는데 약 6분이 걸립니다.

※개인 공부 목적의 정리글입니다.
이 글의 내용이 최선의 해답은 아닐 수 있습니다.

문제

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

<그림 1>

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

<그림 2>

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

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

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

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

입력

입력의 첫째 줄에 계단의 개수가 주어진다.

둘째 줄부터 한 줄에 하나씩 제일 아래에 놓인 계단부터 순서대로 각 계단에 쓰여 있는 점수가 주어진다. 계단의 개수는 300이하의 자연수이고, 계단에 쓰여 있는 점수는 10,000이하의 자연수이다.

출력

첫째 줄에 계단 오르기 게임에서 얻을 수 있는 총 점수의 최댓값을 출력한다.

풀이

조건에 따라 계단을 오르면서 얻을 수 있는 점수의 최댓값을 구하여야한다.

조건3에 의해 마지막 계단을 무조건 밟아야 한다고 한다. 마지막 계단을 밟기 위해서 마지막 계단으로 올라올 수 있는 경우를 따져보자.

먼저 마지막 계단인 N번 계단을 밟기 위해 전전 계단인 N-2부터 한 계단씩 오르는 경우다. 이 경우는 불가능하다! N-2번 계단을 밟고 있는 시점에서 이미 계단을 한 번 밟은 것이라서 N-1번 계단을 밟으면 두 번, N번 계단을 밟으면 세 번으로, 조건2에 위배된다.

전전 계단인 N-2에서 바로 N번 계단으로 오는 경우이다. 이 경우는 가능하다.

바로 전 계단인 N-1번에서 N번으로 올라오려면? 첫 번째 경우에서 봤듯이 N-2에서 출발할 경우 불가능하다. 그러나 N-3에서 N-1로 가면 한 계단을 건너뛰어서 연속해서 밟은 개수가 1이 되고, 그 상태에서 N으로 올라와도 연속해서 2개의 계단을 밟은 것이니 문제없다. 이 경우도 가능하다.

요약해보면, N번 계단에 오르기 위해서는 N-2에서 오거나 N-3에서 N-1을 거친 후 N번 계단에 도달할 수 있다.

점화식은 dp[i] = max(dp[i-3]+arr[i-1], dp[i-2]) + arr[i]로 나타낼 수 있다.

점화식을 풀어서 설명하면, i번 계단에 도달할 때 최고 점수는 i-3번 까지의 최고 점수와 i-1번의 점수의 합과 i-2번 까지의 최고 점수 중 더 큰 값에 i번의 점수를 더한 값이다.

나는 반복문을 이용하는 Buttom-Up 방식으로 풀것이다. 그러기 위해서는 못해도 i-3번에 값이 들어있어야 오류가 안날 것이다. 이를 위해 메모이제이션을 위한 dp배열의 1번과 2번 값은 직접 초기화 해주고, 반복문은 i=3부터 시작한다. dp배열의 0번 값은 계단으로 취급하지 않는 출발점이므로 사용하지 않는다.

dp[1]은 첫 번째 계단 까지의 합인데, 이전에 계단이 없으므로 dp[1]은 첫 번째 계단의 점수와 같다.

dp[2]는 당연히 첫 번째 계단과 두 번째 계단의 점수의 합이다. 주의할 점으로 N이 1이 들어오면 두 번째 계단이 존재하지 않아 오류가 날 것이므로 N이 2 이상인 것을 체크해주고 값을 넣어주어야 한다.

dp[3] 부터는 반복문과 위에서 구한 점화식을 그대로 옮겨주면 된다. 반복을 다 돌았다면 dp[N]에 출력해야할 값이 담겨있을 것이다.

코드

public static void main(String[] args) throws IOException{
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    sb = new StringBuilder();

    int N = Integer.parseInt(br.readLine());
    step = new int[N+1];  // 입력된 각 계단의 점수를 저장할 배열
    dp = new int[N+1];  // i번 계단 까지의 최고 점수를 i번 칸에 저장할 배열
    for(int i=1; i<=N; i++){  // 입력받은 점수를 넣는다
        step[i] = Integer.parseInt(br.readLine());
    }

    // dp[0] = 0;  // int 배열은 기본으로 0으로 초기화되서 이 부분은 필요없음
    dp[1] = step[1];  // 첫번째 계단의 점수와 같다.
    if(N >= 2){  // 계단이 하나만 있는 경우라면 오류가 나므로 계단이 둘 이상일 때만
        dp[2] = step[1] + step[2];  // 두번째 계단 까지의 최고합은 첫번째 계단 점수 + 두번째 계단 점수
    }

    for(int i=3; i<=N; i++){  // i=3부터 N까지 순회
        dp[i] = Math.max(dp[i-3] + step[i-1], dp[i-2]) + step[i];  // 구했던 점화식
    }

    sb.append(dp[N]);  // 결과 출력
    System.out.println(sb.toString());
    br.close();
}

댓글