algorithm - Dynamic

동적계획법

---

유형

1.계단오르기

//문제
철수는 계단을 오를 때 한 번에 한 계단 또는 두 계단씩 올라간다. 만약 총 4계단을 오른다면 
그 방법의 수는 1+1+1+1, 1+1+2, 1+2+1, 2+1+1, 2+2 로 5가지이다. 
그렇다면 총 N계단일 때 철수가 올라갈 수 있는 방법의 수는 몇 가지인가?
//입력
7
//출력
21

public class ex1 {
    public static int solution(int n,int[] dy){
        dy[1]=1;
        dy[2]=2;
        for(int i=3; i<=n; i++){
            dy[i] = dy[i-1] + dy[i-2];
        }
        return dy[n];
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] dy = new int[n+1];
        System.out.println(solution(n,dy));
    }
}

풀이
1.잘 보면 피보나치

2.돌다리 건너기

//문제
개울은 N개의 돌로 다리를 만들어 놓았습니다. 철수는 돌 다리를 건널 때 한 번에
한 칸 또는 두 칸씩 건너뛰면서 돌다리를 건널 수 있습니다. 
철수가 개울을 건너는 방법은 몇 가지일까요?
//입력
7
//출력
34

public class ex2 {
    public static int solution(int n,int[] dy){
        dy[1]=1;
        dy[2]=2;
        for(int i=3; i<=n; i++){
            dy[i] = dy[i-1] + dy[i-2];
        }
        return dy[n-1] + dy[n];
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] dy = new int[n+1];
        System.out.println(solution(n,dy));
    }
}

풀이
1.잘 보면 피보나치
2.개울을 아예 건너야하기 때문에 다음 dy[n+1]의 값을 구해야함.

3.최대부분 증가수열

//문제
N개의 자연수로 이루어진 수열이 주어졌을 때, 그 중에서 가장 길게 증가하는(작은 수에서 큰 
수로) 원소들의 집합을 찾는 프로그램을 작성
//입력
8
5 3 7 8 6 2 9 4
//출력
4 ( 5 7 8 9 , 3 7 8 9 가 젤 길다.)

public class ex3 {
    public static int solution(int n,int[] arr,int[] dy){
        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);
        int n = sc.nextInt();
        int[] arr = new int[n];
        int[] dy = new int[n];
        for(int i=0; i<n; i++){
            arr[i] = sc.nextInt();
        }
        System.out.println(solution(n,arr,dy));
    }
}

풀이
1.수열 길이를 저장할 dy[]를 선언.
2.수열 크기만큼 i가 돌고 j가 해당 i-1위치에서 --로 0까지 돌면서 if (arr[j] < arr[i] && dy[j] > max)에 해당하면 max=dy[j];해준다.
3.dy[i]=max+1;를 해서 길이를 측정한다.

4.가장 높은 탑 쌓기

//문제
밑면이 정사각형인 직육면체 벽돌들을 사용하여 탑을 쌓고자 한다. 탑은 벽돌을 한 개씩 아래
에서 위로 쌓으면서 만들어 간다. 아래의 조건을 만족하면서 가장 높은 탑을 쌓을 수 있는 프
로그램을 작성해라.
//입력
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 s=0,h=0,w=0,n=0;
    static int[] dy;
    public static int solution(ArrayList<Doll> arr){
        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]=arr.get(i).h + max_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];
        ArrayList<Doll> arr = new ArrayList<>();
        for(int i=0; i<n; i++){
            s = sc.nextInt();
            h = sc.nextInt();
            w = sc.nextInt();
            arr.add(new Doll(s,h,w));
        }
        System.out.println(solution(arr));
    }

}

풀이
1.Doll객체를 만들어서 입력되는 s,h,w의 값을 저장한다. 그리고 Comparable로 넓이면적으 큰 돌부터 작은순으로 정렬한다. Collections.sort(arr)도 해준다.
2.최대 높이를 저장할 dy[]배열을 만든다.
3.2중for문으로 우선 돌의개수n만큼 돌고 거기서 j를 해당 i의 앞에서부터0까지 돌린다. 무게가 더 무겁고 높이가 더 높은 돌이면 max_h=dy[j];를 해주고, dy[i]=arr.get(i) + max_h를 해준다.
4.answer=Math.max로 가장 큰 높이를 리턴한다.

5.동전교환(냅색 알고리즘)

//문제
다음과 같이 여러 단위의 동전들이 주어져 있을때 거스름돈을 가장 적은 수의 동전으로 교환
해주려면 어떻게 주면 되는가? 각 단위의 동전은 무한정 쓸 수 있다.
//입력
3
1 2 5
15
//출력
3

public class ex5 {
    static int[] dy;
    static int n=0,m=0;

    public static int solution(int[] coin){
        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) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        int[] arr = new int[n];
        for(int i=0; i<n; i++){
            arr[i] =sc.nextInt();
        }
        m = sc.nextInt();
        dy=new int[m+1];
        System.out.println(solution(arr));
    }
}

풀이
1.입력되는 m만큼 dy[m+1] 배열을 만들어준다. arr 배열을 만들어 동전 종류를 담는다.
2.2중for문으로 동전개수만큼 i로 for문 , coin[i] 만큼 j로 for문을 돌린다.
3.dy[j] 에 Math.min()을 이용해서 더 적은 경우의 수를 넣는다.
핵심
dy[j-coin[i]]+1; 을 이용해서 해당 coin[i]를 포함해서 해당 dy[j]의 경우의 수를 구한다.

6.최대점수 구하기(냅색 알고리즘)

//문제
이번 정보올림피아드대회에서 좋은 성적을 내기 위하여 현수는 선생님이 주신 N개의 문제를 
풀려고 합니다. 각 문제는 그것을 풀었을 때 얻는 점수와 푸는데 걸리는 시간이 주어지게 됩
니다. 제한시간 M안에 N개의 문제 중 최대점수를 얻을 수 있도록 해야 합니다. 
//입력
5 20
10 5
25 12
15 8
6 3
7 4
//출력
41

public class ex6 {
    public static void main(String[] args) {
        Scanner sc= new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        int[] dy=new int[m+1];
        for(int i=0; i<n; i++){
            int score = sc.nextInt();
            int time = sc.nextInt();
            for(int j=m; j>=time; j--){
                dy[j] = Math.max(dy[j],dy[j-time]+score);
            }
        }
        System.out.println(dy[m]);
    }
}

풀이
1.이 문제는 일단 각 문제에 대해서 중복이 안된다. 그래서 dy[]를 순회하는 j가 뒤에서부터 돌아야한다.
2.동전교환과 핵심 로직은 같다. 2중 for문만 유의하자.