algorithm - 냅색 알고리즘

동전 교환

다음과 같이 여러 단위의 동전들이 주어져 있을때 거스름돈을 가장 적은 수의 동전으로 교환
해주려면 어떻게 주면 되는가? 각 단위의 동전은 무한정 쓸 수 있다

//출력
3
1 2 5 -> 동전 종류
15 -> 거스름돈

//입력
3

풀이

public class ex5 {
    static int n,m;
    static int[] coin;
    static int[] dy;
    public static int solution(){
        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();
        coin = new int[n];

        for(int i=0; i<n; i++){
            coin[i]=sc.nextInt();
        }

        m = sc.nextInt();
        dy = new int[m+1];
        System.out.println(solution());
    }
}

dy[i] : i 금액을 만드는데 드는 최소동전 개수
1. dy[]를 구하는 거스름돈 만큼 생성. 후 Integer.MAX로 초기화
2. dy[i]로 for문을 돌려서 i가 1원,2원,5원 일때의 2중 for문 j로 해당 dy[j]에 최소 동전 수를 저장.

핵심 : dy = dy[ j - coin[ i ] ] + 1

최대 점수 구하기

이번 정보올림피아드대회에서 좋은 성적을 내기 위하여 현수는 선생님이 주신 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] : j분으로 얻을수있는 최대 점수
2. 앞서 동전교환 문제처럼 풀게되면 5분 짜리문제를 10분에서 2번풀게된다.
   한 문제를 여러번 푸는 꼴이된다. 한 문제는 한번만 풀수있다. 그래서
   j를 뒤에서 부터 돌리면서 해당 분에서의 최대점수를 기록한다.

핵심 1. : dy[j] = dy[ j - time ] + score
핵심 2. : 중복이 허용되지 않는 경우 겹치지않게 뒤에서 부터 체크한다.