다이나믹 프로그래밍 > 12865번, 9084번, 2293번

12865번

 

 

배낭에 넣을 수 있는 물건들의 가치합의 최댓값을 담은 이차원 배열

 

// knapsack 알고리즘 > 무게와 가치가 함께 주어짐
// 이차원 배열 사용

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class baekjoon12865 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        int n = Integer.parseInt(st.nextToken());
        int k = Integer.parseInt(st.nextToken());

        int [][] dp = new int[n+1][k+1];
        int [] weight = new int[n+1];
        int [] value = new int[n+1];

        for(int i = 1; i<=n; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            weight[i] = Integer.parseInt(st.nextToken());
            value[i] = Integer.parseInt(st.nextToken());
        }

        for(int i = 1; i<=n; i++) { // 1번 물품, 2번 물품, 3번 물품...
            for(int j = 1; j<=k; j++) { // 1kg, 2kg, 3kg...
                if(j >= weight[i]) {
                    dp[i][j] = Math.max(dp[i-1][j], dp[i-1][j-weight[i]]+value[i]);
                } else {
                    dp[i][j] = dp[i-1][j]; // 이전 물품의 가치를 저장
                }
            }
        }
        System.out.println(dp[n][k]);
    }
}

 

9084번

 

 

가지고 있는 동전의 종류(1, 2, 5원)로 각각의 금액을 만드는 경우의 수를 담은 이차원 배열

 

// 이차원 배열을 사용한 풀이

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class baekjoon9084 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int test = Integer.parseInt(br.readLine());
        StringTokenizer st;
        StringBuilder sb = new StringBuilder();
        for(int i = 0; i<test; i++) {

            int n = Integer.parseInt(br.readLine());

            int [] coin = new int[n+1];

            st = new StringTokenizer(br.readLine(), " ");

            for(int j = 1; j<=n; j++) {
                coin[j] = Integer.parseInt(st.nextToken());
            }

            int amount = Integer.parseInt(br.readLine()); // 만들어야 할 금액

            int [][] dp = new int[n+1][amount+1];
            for(int j = 1; j<=n; j++) {
                dp[j][0] = 1; // 0번째 열은 모두 1로 초기화
                // 어떤 동전이든 0원을 만들 수 있는 가지수는 무조건 1가지 존재 > ex : 1원 동전 0개로 0원을 만들 수 있음
            }

            for(int j = 1; j<=n; j++) {
                for(int h = 1; h<=amount; h++) {
                    if(h>=coin[j]) {
                        dp[j][h] = dp[j-1][h] + dp[j][h-coin[j]];
                    } else {
                        dp[j][h] = dp[j-1][h]; // h원을 만들기 위해 동전 coin[j]를 사용할 수 없는 경우 > 기존에서 추가되는 경우의 수 없음
                    }
                }
            }

            sb.append(dp[n][amount]+"\n");

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

 

2293번

 

 

가지고 있는 동전의 종류(1, 2, 5원)로 각각의 금액을 만드는 경우의 수를 담은 일차원 배열

 

첫 번째 : 1원만 사용한 경우 / 두 번째 : 1원과 2원을 사용한 경우 / 세 번째 : 1원, 2원, 5원을 사용한 경우

 

// 시간 제한 조건 때문에 이차원 배열이 아닌 일차원 배열로 풀이

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class baekjoon2293 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        int n = Integer.parseInt(st.nextToken());
        int k = Integer.parseInt(st.nextToken());
        int [] coin = new int[n+1];
        for(int i = 1; i<=n; i++) {
            coin[i] = Integer.parseInt(br.readLine());
        }
        int [] dp = new int[k+1];
        dp[0] = 1;
        for(int i = 1; i<=n; i++) {
            for(int j = coin[i]; j<=k; j++) {
                dp[j] = dp[j] + dp[j-coin[i]];
            }
        }
        System.out.println(dp[k]);
    }
}