[백준] 1480 보석모으기 - Java

 

 

문제출저

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

1480번: 보석 모으기

 

 

 

문제풀이 

주어진 가방을 이용해 최대한 많은 보석을 담는 방법을 구하는 문제이다.

이를 위해 중복을 줄여주는 비트마스크와 다이나믹프로그래밍, 완전탐색을 위한 DFS를 활용한다.

 

 

int MAX = 14;
dp = new int[1 << MAX][11][21];

1 << MAX : 

A << B의 의미는 정수 A을 왼쪽으로 B만큼 이동한다는 뜻 이다.

알고리즘적으로 MAX의 수 14만큼 비트들을 만들라는 뜻으로 받아들였다.

 

예) 1 << 5 이면 visited = new boolean[5]; 라 이해함.

 

 

if(path & (1 << i)) > 0 ) continue;

path & (1 << i) 

& 는 and 연산자로 A & B 인 경우 A,B 중 하나라도 0이 있으면 0이 나온다. 즉 1이 나올려면 A와 B가 모두 1이어야 한다. 

path & (1 << i) 가 1이 나오기 위해서는 path 와 (1 << i)가 일치해야 한다.

즉 저 조건문은 보석들을 담은 경우의 수가 같으면 넘어간다는 의미이다.

 

예) 1 -> 2 -> 4 순서로 보석을 담으면 비트마스크는 1011, 2 -> 1 -> 4 순서로 보석을 담아도 비트마스크는 1011이다. 이러한 중복을 방지해준다.

 

 

 if(cap >= board[i])
{
    dp[path][idx][cap] = Math.max(dp[path][idx][cap], dfs(path | (1 << i), idx, cap - board[i]) + 1);
}

위의 조건문은 남은 가방 용량이 다음에 탐색한 보석의 무게보다 크거나 같으면 담는다는 의미이다.

이 때 | 비트 연산자가 사용된다.

| 비트는 A | B 중 A,B 둘 중 하나가 1이면 1이 나온다.

path | (1 << i) 의 의미는 path에 i를 추가해 경로를 확장한다는 의미이다.

 

 

 

 

 

소스코드

package studyGroup.july.july23;

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

/*

bitmast + dp

 */


public class 백준1480보석모으기 {

    static int MAX = 14; // 보석의 개수 n은  13보다 작거나 같다.
    static int n, m, c;
    static int[] board;
    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()); // 가방의 개수
        c = Integer.parseInt(st.nextToken()); // 가방의 최대 한도

        board = new int[n];

        // 1 << max : max개의 비트를 생성한다. <<은 정수1을 왼쪽으로 14만큼 이동이라는 뜻 이다.
        // 보석의 크기는 13보다 작다 -> 1 << max
        // 보석의 크기는 10보다 작다. -> 11
        // 가방의 최대한도는 20보다 작다 -> 21
        dp = new int[1 << MAX][11][21];

        st = new StringTokenizer(br.readLine());
        for(int i = 0; i < n; i++)
        {
            board[i] = Integer.parseInt(st.nextToken());
        }

        int answer = dfs(0,0,c);
        System.out.println(answer);


    }

    // path : 탐색한 보석의 index
    // idx : 가방의 순서
    // k : 쓸 수 있는 가방의 용량 (남아 있는 양)
    public static int dfs(int path, int idx, int cap) {


        // 모든 보석이나, 모든 가방을 사용했다면 return
        if(( (path == (1<<n)-1) || idx == m ))
        {
            return 0;
        }


        // 이미 방문한 곳이면
        if(dp[path][idx][cap] != 0) {
            return dp[path][idx][cap];
        }

        for(int i = 0; i < n; i++)
        {
            // 이미 사용된 보석이면 넘어감
            if( (path & (1 << i)) > 0)
            {
                continue;
            }


            // 가방에 담을 수 있다면 가방에 담고 계속 탐색
            if(cap >= board[i])
            {
                dp[path][idx][cap] = Math.max(dp[path][idx][cap], dfs(path | (1 << i), idx, cap - board[i]) + 1);
            }
            // 가방에 담을 수 없다면 다음 가방을 선택하고 탐색 
            else
            {
                // 용량이 조금 남았더라도, 다음 가방(idx + 1) 탐색
                dp[path][idx][cap] = Math.max(dp[path][idx][cap], dfs(path, idx+1, c));
            }


        }


        return dp[path][idx][cap];

    }

}

 

 

 

참조

https://coder-in-war.tistory.com/entry/BOJ-JAVA1480-%EB%B3%B4%EC%84%9D%EB%AA%A8%EC%9C%BC%EA%B8%B0

[ BOJ ][JAVA][1480] 보석모으기

 

 

감사합니다.