[인프런/LIS/가장 높은 탑 쌓기]

오늘은 LIS(최대부분 증가수열 알고리즘)을 활용한 알고리즘 문제를 풀어보았다.

 

우선적으로 특정 한 부분을 정렬을 하고 시작하면 원활하게 풀 수 있는 문제였다.

 

하지만 이 문제를 제대로 풀기 위해서는 객체를 정렬하는 방법에 대해 알아야 하고, 아래에 사용하고 있는 dy의 개념을 잘 파악해야 한다.

 

<<풀이>>

import java.util.ArrayList;
import java.util.Collections;
import java.util.Scanner;

class Brick implements Comparable<Brick> {

    public int s, h, w;
    Brick(int s, int h, int w) {
        this.s = s;
        this.h = h;
        this.w = w;
    }

    @Override
    public int compareTo(Brick o) {
        return o.s - this.s;
        // 이게 내리차순 형식
    }
}


class Main {
    static int[] dy;
    int solution(ArrayList<Brick> arr) {
        int answer = 0;
        Collections.sort(arr);
        dy[0] = arr.get(0).h;
        answer = dy[0];
        for (int i = 1; i < arr.size(); i++) {
            int max_h = 0;
            for (int j = i-1; j >=0 ; j--) {
                if(arr.get(i).w < arr.get(j).w && dy[j] > max_h) {
                    max_h = dy[j];
                }
                dy[i] = arr.get(i).h + max_h;
                answer = Math.max(answer, dy[i]);
            }
        }
        return answer;
    }



    public static void main(String[] args) {
        Main T = new Main();
        Scanner in = new Scanner(System.in);

        int n = in.nextInt();

        ArrayList<Brick> arr = new ArrayList<Brick>();
        dy = new int[n];
        for (int i = 0; i < n; i++) {
            int a = in.nextInt();
            int b = in.nextInt();
            int c = in.nextInt();
            arr.add(new Brick(a, b, c));
        }

        System.out.println(T.solution(arr));



    }
}

 

 

1. 우선 값들을 넣을 클래스 하나를 만들어 준다.(Brick)

2. implements로 Comparable 추상 클래스를 가져온다.

3. 그다음 compareTo 메서드를 재정의 해준다.

4. Brick.o - this.o 는 내림차순 this.o - Brick.o 는 오름차순이다.

5. 내림차순으로 만드는 형태로 한다.

6. 그다음 solution 메서드 내부에서 알고리즘을 구상하는데, Collection.sort()로 객체를 정렬한다.

7. dy 배열을 활용해서 각 객체가 자기가 갈 수 있는 최대 높이의 값을 구한 뒤, dy에다가 넣어준다.

8. dy를 넣어주는 과정에서 Math.max 로 answer 값을 추출한다.

 

전체적으로 이러한 구성으로 알고리즘을 풀어나가면 된다.

 

어떻게 보면 쉬운 문제일 수도 있지만, 처음 하면 약간은 헷갈릴 수도 있고 그로인해 와닿지 못할 수도 있다.

 

나도 이해는 했지만 만약 혼자 다시 풀어라고 한다면 풀 수는 있지만 조금 느릴 수도 있다고 생각한다.

 

결국, 반복된 공부로 익숙해지고 여러 문제를 풀면서 논리적인 사고를 길러 나간다면 충분히 해결할 수 있다고 본다.