[백준] 6144 Charm Bracelet - Java

 

 

 

문제 출저

https://www.acmicpc.net/problem/6144

6144번: Charm Bracelet

 

 

 

문제 풀이

보석의 종류 n, 가질 수 있는 무게 m이 주어집니다. 각각의 보석은 무게(w), 매력도(c)를 가지고 있습니다. m 무게 내에서 최대의 매력도를 구해야 합니다.

 

배낭 문제를 이용하여 문제를 풀었습니다.

1차원 int 배열 dp를 이용합니다.

점화식은 다음과 같습니다. 

dp[j] = Math.max(dp[j], dp[j - w] + d);

 

이 보석을 선택했을 때의 매력도와 기존의 매력도를 비교해서 큰 값을 메모리에 저장하는 방식입니다. 

 

 

 

소스 코드

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

/*
Charm Bracelet
https://www.acmicpc.net/problem/6144

배낭 문제
 */

public class Main {

    static int n;
    static int m;
    static int[] dp;

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());

        dp = new int[m+1];
        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            int w = Integer.parseInt(st.nextToken());
            int d = Integer.parseInt(st.nextToken());

            for (int j = m; j >= 0; j--) {
                if (j - w >= 0) {
                    dp[j] = Math.max(dp[j], dp[j - w] + d);
                }
            }
        }

        System.out.println(dp[m]);



    }

}