[문제풀이] 10-04. 가장 높은 탑 쌓기

인프런, 자바(Java) 알고리즘 문제풀이

Dynamic Programming - 1004. 가장 높은 탑 쌓기

🗒️ 문제

🎈 나의 풀이

	private static class Brick implements Comparable<Brick> {
        int a, h, w;

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

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

    private static int solution(List<Brick> list) {
        Collections.sort(list);
        int[] dy = new int[list.size()];
        dy[0] = list.get(0).h;

        for(int i=1; i<list.size(); i++) {
            int height = list.get(i).h;

            for(int j=0; j<i; j++) {
                if(list.get(j).w > list.get(i).w) {
                    height = Math.max(height, dy[j] + list.get(i).h);
                }
            }
            dy[i] = height;
        }

        return Arrays.stream(dy).max().getAsInt();
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        List<Brick> list = new ArrayList<>();

        for(int i=0; i<n; i++) list.add(new Brick(sc.nextInt(), sc.nextInt(), sc.nextInt()));

        System.out.println(solution(list));
    }

🖍️ 강의 풀이

  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;
      public 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(j).w > arr.get(i).w && dy[j]>max_h){
                      max_h=dy[j];
                  }
              }
              dy[i]=max_h+arr.get(i).h;
              answer=Math.max(answer, dy[i]);
          }
          return answer;
      }

      public static void main(String[] args){
          Main T = new Main();
          Scanner kb = new Scanner(System.in);
          int n=kb.nextInt();
          ArrayList<Brick> arr=new ArrayList<>();
          dy=new int[n];
          for(int i=0; i<n; i++){
              int a=kb.nextInt();
              int b=kb.nextInt();
              int c=kb.nextInt();
              arr.add(new Brick(a, b, c));
          }
          System.out.print(T.solution(arr));
      }
  }

💬 짚어가기

해당 문제는 그래프의 Dynamic Programming(동적 계획법)을 통해 풀 수 있다.
앞에서 풀이한 최대 부분 증가 수열문제와 동일한 로직이다. 이젠 문제에서 한 가지 추가된 점으로
면적 또는 무게 중 한 가지 기준에 대해 정렬을 수행한 후 가장 높은 탑의 높이를 구할 수 있다.
( 자세한 풀이는 최대 부분 증가 수열 문제 참고 )