백준(BOJ) 2655: 가장높은 탑쌓기

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

가장높은 탑쌓기: 최장증가 부분수열(LIS, Longest Increaing Subsequence) 문제의 변형

기존과 비슷한 문제여서 기존의 방법으로 뭔가 해결될 수 있을 것 같으면 해보면 된다. 다만 용납해서는 안되는 경우가 같은 문제임에도 불구하고 전혀 다른 풀이를 쓰고 기존의 해결방법을 적용할 줄 모르는 것이다.

만약 기존의 풀이법으로는 안된다면 왜 안되는지 파악해야 한다. 그것이 기존의 문제와 다른 차이점이기 때문이라면 차이점은 명확히 정리해서 알고있어야 한다. 그게 문제를 정리해 가는 것이므로.


대체 어떻게 했길래 dp[i]가 i번째 벽돌을 가장 아래에 뒀을때의 최대높이를 의미하게 할 수 있었던 것인가?
(0-1배낭문제)대체 어떻게 했길래 dp[i][j]가 i번째 보석을 고려했을때 최대가치를 의미하게 할 수 있었던 것인가? 

==>>매번 그런의미를 가질수 있는 적절하게 만든 조건식을 통과한 결과만을 차곡차곡 쌓아왔기 때문이다. 

이 문제는 0-1배낭문제와 닮은 구석(모든벽돌을 사용하지 않아도 된다는 점, 제한 조건이 있다는 점)이 있지만 다른구석도 있다. 바로 어떠한 일정한 주머니라는 제한조건안에 담는 것은 아니라는 점이다.( 0-1배낭문제는 어떤 것을 담을시에 가방이 감당할수 있는 무게가 그만큼 줄어 들어 해당 슬롯의 값을 찾아가지만(V[i-1, w-wi]) 여기서는 그런것 같지 않아 해결의 실마리를 잡지 못하겠다).

해법은 배낭문제하고는 전혀 달랐다. 하지만 dp에는 최대높이를 담는다는내 생각은 맞았다. 모든 벽돌을 하나씩 확인하면서 dp를 갱신해야한다는 해법도 내가 생각했던 것과 같았다

0-1배낭문제에서 dp의 값으로는 해당행 까지의 보석을 고려했을때의 가치의 최댓"값"이 들어가지만 가장 높은 탑쌓기 문제에서의 dp값에는 해당 행의 벽돌을 가장 아래에 두었을때의 최대높이"값"이 들어간다. 두 문제 모두 답으로 요구하는 성질의 그 '값' 이 들어가지마 어떠한 성질, 어떠한 조건이 충족되는 "값"이 들어가는지는 다른것이다.  어떠한 성질의 값이 들어가는지는 조건문(if (bricks[i].s > bricks[j].s)) , 실제로 어떤 값을 주는지(dp[i] = Math.max(dp[i], dp[j] + bricks[i].h)),  그리고 심지어는 정답의 구성요소가 되는 부분을 사전에 정렬했는지( Arrays.sort(bricks);) 마저 영향을 끼친다.

 

위의 것은 어디까지나 문제 해결의 팁이고 중요한 것은 내가 자율적으로 이문제가 다른문제와 어떻게 변별되는지 그 차이점과 공통점을 파악하는 것이다.

우선 문제에서는 맞춰주어야 하는 조건이 2개(무게, 밑면의 넓이)이다 보니 문제를 수월하게 생각하기 위해 그 중하나를 정렬을 이용하여  해결하고 들어간다.

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.lang.reflect.Array;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.StringTokenizer;

public class Testing3 {
    static class Brick implements Comparable<Brick> {
        public Brick(int n, int s, int h, int w) {
            this.n = n;
            this.s = s;
            this.h = h;
            this.w = w;
        }

        int n;
        int s;
        int h;
        int w;

        @Override
        public int compareTo(Brick o) {
            return this.w - o.w;
        }
    }

    /*
    dp[i]는 i번째 벽돌을 가장 아래두었을 때의 높이. 어떻게 이런 의미를 가질 수 있나? 우선은 bricks배열이 무게를 기준으로
    정렬되었다. 그리고 밑넓이 또한 bricks[i].s>bricks[j].s 를 만족해야 하므로 어디에도 i번째 벽돌을 가장 아래에 두게하는
    코드가 없지만 위와같은 정렬과 조건문을 통해 i번째 벽돌이 가장 아래에 두어진다고 한들 아무런 모순이 생기지 않기 때문에
    dp[i]가 i번째 벽돌을 가장 아래에 둔다는 것을 의미할 수도 있는 것이다. 사실은 오름차순으로 정렬되었다는것이 곧 가장
    아래에 둔다는 의미를 만들어 준다.
     */
    public static void solution(int n, Brick[] bricks) {
        Arrays.sort(bricks);
        int[] dp = new int[n + 1];
        for (int i = 1; i <= n; ++i) {
            for (int j = 0; j < i; ++j) {
                if (bricks[i].s > bricks[j].s) {
                    dp[i] = Math.max(dp[i], dp[j] + bricks[i].h);
                }
            }
        }

        int maxValue = -1;
        int i = n;

        while (i != 0) {
            if (dp[i] > maxValue) maxValue = dp[i];
            --i;
        }

        List<Integer> answer = new ArrayList<>();
        int index = n;
        while (index != 0) {
            if (maxValue == dp[index]) {
                answer.add(bricks[index].n);
                maxValue -= bricks[index].h;
            }
            --index;
        }

        int size = answer.size();
        System.out.println(size);
        for (int k = size - 1; k >= 0; --k)
            System.out.println(answer.get(k));
    }

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        Brick[] arr = new Brick[n + 1];
        arr[0] = new Brick(0, 0, 0, 0);
        StringTokenizer st;
        for (int i = 1; i <= n; ++i) {
            st = new StringTokenizer(br.readLine());
            int s = Integer.parseInt(st.nextToken());
            int h = Integer.parseInt(st.nextToken());
            int w = Integer.parseInt(st.nextToken());
            arr[i] = new Brick(i, s, h, w);
        }
        solution(n, arr);
    }
}

답을 구하는 방법이 이전모든 방식과는 다르게 독특하다. 
특정 벽돌을가장 아래에 두었을때의 최대높이를 벽돌별로 구한다. 즉 dp[1]는 1번벽돌을 가장 아래두었을때의 최대높이를 의미하고, dp[4]는 4번벽돌을 가장 아래두었을때의 최대높이를 의미한다. 다만 한가지 주목할 것은 각각의 dp인자들(dp[4], dp[1]...)은 무게와 밑면의 규칙을 지켜가며 탑을 쌓아 올렸다는 것이다. 


dp[i]는 i번째 벽돌을 가장 아래두었을 때의 높이. 어떻게 이런 의미를 가질 수 있나? 우선은 bricks배열이 무게를 기준으로  정렬되었다. 그리고 밑넓이 또한 bricks[i].s>bricks[j].s 를 만족해야 하므로 어디에도 i번째 벽돌을 가장 아래에 두게하는 코드가 없지만 위와같은 정렬과 조건문을 통해 i번째 벽돌이 가장 아래에 두어진다고 한들 아무런 모순이 생기지 않기 때문에 dp[i]가 i번째 벽돌을 가장 아래에 둔다고 말할수도 있는 것이다. 사실은 오름차순으로 정렬되었다는것이 곧 가장 아래에 둔다는 의미를 만들어 준다.

문제는 여러번 풀어서 익히기는 했지만 다음에 또 접할때 못풀때는 아래 그림을 참고하면 많은 도움이 될것이다.

https://fastcampus.co.kr/courses/210773/clips/

 

그냥 쉽게 생각하면 이처럼 쉬운 문제가 없다. 어쨋든 규칙은 지켜가면서 탑을 쌓아야 하는 것이므로 주된 관점은 반복문을 진행할 때 그때마다 진행되는 벽돌을 가장 아래에 넣는 경우를 당위적으로 생각해 주는 것이다. 그런경우 무게, 면적의 조건은 물론 만족시켜야 하는 것이고. 상식적으로 해당블럭을 가장 위에 놓고 조건을 생각해 줄수는 없잖아? 당연히 가장 아래에 넣는 경우를 생각하고 거기서 최적의 원리를 적용한 식을 만들 생각을 하면된다. 

또한 생각해 볼것이 이문제는 LIS(Longest Increasing Subsequence)의 심화확장 문제라고 했으니 두문제를 당연 비교해 봐야한다.