동적 계획 알고리즘 -(2)

동적 계획 알고리즘 -(2)

10-3. 최대 부분 증가수열

• dy[i] 에 올 수 있는 값

= 자기 보다 앞에있는 애들 中 자기보다 작으면서 최댓값 갖는 애 찾고 +1

import java.util.Scanner;

/* 10-3. 최대부분증가수열 LIS */ 
public class Main1 {
    static int[] dy;
    //솔루션 함수 
    static int solution(int [] arr) {
        int answer = 0;
        dy = new int[arr.length];
        dy[0]=1; //최초값은 길이 1
        answer = dy[0];//길이1 짜리 들어오는 것 대비

        //dy[i]에 담을 길이 = 처음 ~ i 직전까지 앞배열 탐색 아며
        //현재 arr[i]보다 값은 작으면서 길이 dy[]는 최대 갖는 애를 찾고 +1 
        for(int i=1; i<arr.length; i++) {
            int max = 0;
            for(int j= i-1; j>=0; j--) {
                if(arr[i] > arr[j] && dy[j] > max) max = dy[j];
            }
            //현재의 i 길이는 (자기보다 작은애들 중) 앞에서의 최대 길이 + 1
            dy[i] = max + 1; 
            //이제 answer = 기존 answer 보다 더 큰 dy[]나타나면 갱신됨
            answer = Math.max(answer, dy[i]);
        }
        return answer;
    }
    //실행 메인 
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        Main1 T = new Main1();
        Scanner kb= new Scanner(System.in);

        int n = kb.nextInt();
        int[] arr = new int[n];
        for(int i=0; i<n; i++) {
            arr[i] = kb.nextInt();
        }

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

---

10-4. 가장 높은 탑 쌓기

• dy[i] = i번째 벽돌을 top 에 놓았을 때 가능한 최대 높이 값

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

/* 10-4. 가장 높은 탑 쌓기  */
//벽돌 Brick 객체
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) {
        // TODO Auto-generated method stub
        return o.s - this.s; //면적 내림차순 정렬 
    }
}
public class Main2 {
    static int[] dy;

    //솔루션 함수 
    public int solution(ArrayList<Brick> arr) {
        int answer= 0;
        //s 면적 기준 내림차순 정렬
        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;//직전 최대 + 현재 i의 높이 더해주고
            answer = Math.max(answer, dy[i]);
        }
        return answer;
    }
    //실행 메인 
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        Main2 T = new Main2();
        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.println(T.solution(arr));
    }
}

---

10-5. 동전 교환 | 냅색 알고리즘

• dy[i] = i 원 금액 만드는 최소 동전 개수

import java.util.Arrays;
import java.util.Scanner;

/* 10-5. 동전 교환 (냅색 알고리즘) */
public class Main3 {
    static int n, m;
    static int[] dy;
    //솔루션
    public int solution(int[] coin) {
        //우선 dy 내부는 최대값으로 담기 
        Arrays.fill(dy, Integer.MAX_VALUE);
        dy[0] = 0;
        for(int i=0; i<n; i++) {
            for(int j=coin[i]; j<=m; j++) {
                dy[j] = Math.min(dy[j], dy[j-coin[i]]+1);
            }
        }
        return dy[m];
    }

    //실행 메인 
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        Main3 T = new Main3();
        Scanner kb = new Scanner(System.in);
        //동전개수 
        n = kb.nextInt();
        int[] arr= new int[n];
        for(int i=0; i<n; i++) {
            //동전 종류
            arr[i] = kb.nextInt();
        }
        //금액
        m = kb.nextInt();
        dy = new int[m+1];

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

---

10-6. 최대 점수 구하기 | 냅색 알고리즘

• dy[j] = j분 주어졌을 떄 풀 수 있는 최대 점수

import java.util.Scanner;

/* 10-6. 최대점수 구하기 (냅색 알고리즘) */
public class Main4 {
    //실행 메인 
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        Scanner kb= new Scanner(System.in);
        int n = kb.nextInt();
        int m = kb.nextInt();
        int[] dy = new int[m+1];

        for(int i=0; i<n; i++) {
            //각 문제에 ps 점수, pt 시간 담기 
            int ps = kb.nextInt();
            int pt = kb.nextInt();
            for(int j =m; j>=pt; j--) {
                dy[j] = Math.max(dy[j], dy[j-pt]+ps);
            }
        }  
        System.out.println(dy[m]);
    }
}