백준(BOJ) 2579: 계단 오르기

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

이 문제를 풀게 되면서 하게 되는 생각이지만 2개이상의 선택지 중에 선택을 해야 하는 상황이 오면 DP는 탐욕적 알고리즘의 사고를 포함하게 된다. (이것은 0-1배낭문제 등 여러문제에서 확인할 수 있다)

(아래는 0-1배낭문제 에서 나온 말이다. 2개이상의 선택지 중에 최선을 선택해야 하는 상황이 0-1배낭문제에는 존재하고 dp[i][j]는 그때의 무게에서 배낭에 넣을 수 있는 최대가치가 들어가게 된다.

)
(나는 가끔가다 0-1배낭 문제에서 이런 걱정을 하곤한다. 점화식으로 dp 테이블을 채워나가던중 중간단계쯤에서 어떤 아이템이 등장하고 그 아이템의 무게는 이전 아이템들에 비해 정말 가볍고 가치는 엄청나다. 그런데 그 가벼운 무게를 담을 수 없을 정도로 가방의 남아있는 용량이 없다. 그래서 지금까지는 최적의 해를 구해왔지만 이제는 최적을 구할 수 없게 될 수도 있지 않을까? ==>>0-1 배낭문제의 점화식의 특성을 제대로 이해하지 못해서 생기는 걱정이다. 점화식을 보면 해당 아이템을 담았을시에 그 무게를 뺀 경우의 최적해를 부분해로 가져오고 있다(Vi +A[i-1][w-wi]). 이 경우를 물건을 넣지않았을때의 최적의 경우(A[i-1, w])와 비교하고 있는 것이다.)

처음에는 호기롭게 마지막 조건때문에 입력을 거꾸로 배열로 받고 하는것들의 문제의 의도에 맞는 풀이라고 생각했다. 내가 딱히 점화식을 구하지 않아야지! 하고 생각한게 아니다. 나름 주관을 세우고 문제를 풀다보니 점화식을 쓰지 않고 알고리즘이 짜졌고 예시답안은 통과했으나 정답으로 처리되지는 못하였다. 사실 아직 왜 아래 내가 세운 코드로 했을 때 정답이 나오지 않는지 아직 모르겠다. 

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

public class Testing3 {
    public static void solution(int n, long[]arr){
        long answer=arr[1];
        int count=1;
        int position=1;
        //position=n이면 첫번째 계단의 위치이고 position=n+1이면 출발 점의 위치이다. 둘다 있을수 있는 위치이고
        //계단은 한회에 최대 2개까지밖에 오르지 못하므로 이렇게 조건문을 구성하는게 적절하다
        while(position<n){
            if(count==2){
                count=0;
                position+=2;
            }
            else if(arr[position+2]>arr[position+1]){
                count=0;
                position+=2;
            }
            else{
                count+=1;
                position+=1;
            }
            answer+=arr[position];
        }
        System.out.println(answer);
    }
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n=Integer.parseInt(br.readLine());
        long[]arr=new long[n+2];
        /*도착 계단은 반드시 밟아야 한다는 조건이 있다. 이에 따라 아예 도착 계단을 출발점으로 생각하고 처음에 문제에서 주어지는 값을
         배열의 마지막에 오게 하였다. 그러면 마지막에 주워지는 값이 idx=1인 위치에 오게 되고 나는 i=1부터 시작하면 된다.
         */
        for(int i=1;i<=n;++i)
            arr[n-i+1]=Integer.parseInt(br.readLine());

        solution(n, arr);
    }
}

문제에서는 딱히 최적해가 부분해로 구성되어 있지도 않고 점화식도 쓰이지 않는다. 다만 작은 것부터 시작해(한 두 계단씩 오르는것) 도착점까지 가는 과정이 dp의 성격과 닮아있다. ==>> 아... 이러면 안된다. 최적해가 부분해로 구성되어 있지 않다고 잘못생각해서 점화식을 구하지 못하는 것으로 생각하면 안된다. 한칸 혹은 두칸을 오를 수 있다는 것과 연속된 세 개의 계단을 밟아서는 안된다 라는 두가지 미심쩍은 조건을 보고 DP라고 눈치 긁어야 한다. 

An= Max(An-3+value(n-1), An-2)  + value(n)

An=Max(An-2, An-3+value(n-1) ) + value(n)


이렇게 어떠한 특정 단계의 최적해를 구해줄때 이전 부분해들 간의 비교를 통해(Max) 최적해를 구하는 상황에서 나는 이런 생각이 든다. 지금 이 특정 단계에서는 최적해를 구했지만 다음 단계의 최적해를 구할때는 이전 단계의 부분최적해 때문에 이번 최적해를 구하지 못하면 어떻하지? 이 생각은 물론 잘못된 것이다. 왜 잘못되었나? 매순간최적해를 구할때 이전 부분해들의 최적해들 간의 항상 비교가 일어나고 내가 구했던 그 이전 최적 부분해는 똑같은 방식을 거쳐 최적해로 구해진 부분해들이기 때문이다. 

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

public class Testing3 {
    public static void solution(int n, int[]arr){
        int[]dp=new int[301];
        dp[1]=arr[1];
        dp[2]=arr[1]+arr[2];
        dp[3]=Math.max(arr[2], dp[1])+arr[3];
        for(int i=4;i<=n;++i)
            dp[i]=Math.max(dp[i-3]+arr[i-1], dp[i-2])+arr[i];
        System.out.println(dp[n]);

    }
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n=Integer.parseInt(br.readLine());
        int[]arr=new int[301];
        for(int i=1;i<=n;++i)
            arr[i]=Integer.parseInt(br.readLine());


        solution(n, arr);
    }
}

마지막으로 주의할점: n=1일 경우 arr[2]는 배열의 크기보다 큰 색인이므로런타임 에러 (ArrayIndexOutOfBounds)  가발생할수 있음에 주의. 뭐 배열의 크기를 문제의 조건에 맞추어 301로 해주지 않아도 되지만 그렇게 하면 코드 세세하게 다시짜야함. 그러는것 보다 301로 크기 정해 주는게 깔끔.