algorithm - LIS (최대 부분 증가 수열)

Seongjin Jo·2023년 2월 21일
0

algorithm

목록 보기
16/17
post-thumbnail

1. 최대부분 증가수열

N개의 자연수로 이루어진 수열이 주어졌을 때, 그 중에서 가장 길게 증가하는(작은 수에서 큰 
수로) 원소들의 집합을 찾는 프로그램을 작성하라. 

//입력
8
5 3 7 8 6 2 9 4
//출력
4

풀이

public class ex3 {
    static int n;
    static int[] arr;
    static int[] dy;
    public static int solution(){
        int answer=0;
        dy[0]=1;
        for(int i=0; i<n; i++){
           int max=0;
           for(int j=i-1; j>=0; j--){
               if(arr[j]<arr[i] && dy[j]>max) max=dy[j];
           }
            dy[i]=max + 1;
            answer = Math.max(answer,dy[i]);
        }
        return answer;
    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        n = sc.nextInt();
        arr = new int[n];
        dy = new int[n];
        for(int i=0; i<n; i++){
            arr[i] = sc.nextInt();
        }
        System.out.println(solution());
    }
}

  1. 각각의 경우에서의 최댓값을 저장할 dy[]를 생성한다.
  2. arr을 입력받고 2중 for문으로 j=i-1로 가면서 해당 i의 경우에서의 최댓값을 구하는 for문을 돌린다.
  3. 그 중에서의 최대값을 구해서 answer 리턴.

2. LIS 활용 - 가장 높은 탑 쌓기

밑면이 정사각형인 직육면체 벽돌들을 사용하여 탑을 쌓고자 한다. 탑은 벽돌을 한 개씩 아래
에서 위로 쌓으면서 만들어 간다. 아래의 조건을 만족하면서 가장 높은 탑을 쌓을 수 있는 프
로그램을 작성하시오. 

(조건1) 벽돌은 회전시킬 수 없다. 즉, 옆면을 밑면으로 사용할 수 없다.
(조건2) 밑면의 넓이가 같은 벽돌은 없으며, 또한 무게가 같은 벽돌도 없다.
(조건3) 벽돌들의 높이는 같을 수도 있다.
(조건4) 탑을 쌓을 때 밑면이 좁은 벽돌 위에 밑면이 넓은 벽돌은 놓을 수 없다.
(조건5) 무게가 무거운 벽돌을 무게가 가벼운 벽돌 위에 놓을 수 없다.

//입력
5
25 3 4   --> 밑면넓이 , 높이 , 무게
4 4 6
9 2 3
16 2 5
1 5 2

//출력
10

풀이

class Doll implements Comparable<Doll>{
    int s;
    int h;
    int w;

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

    @Override
    public int compareTo(Doll o) {
        return o.s - this.s;
    }
}
public class ex4 {
    static int n;
    static ArrayList<Doll> arr;
    static int[] dy;

    public static int solution(){
        int answer=0;
        Collections.sort(arr);
        dy[0] = arr.get(0).h;
        for(int i=0; i<n; 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) {
        Scanner sc = new Scanner(System.in);

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

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

  1. 위 그림과 같이 s,h,w를 담는 Doll객체를 만들어준다. 그리고 입력을 담는다.
  2. Doll객체를 밑면의 넓이 순으로 정렬한다.
  3. 2중 for문을 이용해 순차적으로 각 돌의 위치에서의 최대높이를 측정한다. 이때 arr.get(j).w 가 arr.get(i).w 보다 무거워야 한다.

0개의 댓글