📙[Algo] 24.05.20 알고리즘

알고리즘 문제) BOJ 1480. 보석 모으기

• 링크 : https://www.acmicpc.net/problem/1480

문제 요약

• 가방 개수에 제한이 있고, 한 가방에 넣을 수 있는 보석 개수에 제한이 있음
• M개의 가방을 갖고 있으며, 각각의 가방은 C그램의 보석을 담을 수 있음
• 보석이 N개 있을 때, 훔칠 수 있는 보석의 최대 개수는?

시간 제한

• 2초

입력

• 보석 개수 N, 가방 개수 M, 가방 최대 한도 C
  • 1 ≤ N ≤ 13, 자연수
  • 1 ≤ M ≤ 10, 자연수
  • 1 ≤ C ≤ 20, 자연수
• 보석 무게가 하나씩 주어짐
  • 1≤ 보석 무게 ≤ 20 자연수

출력

• 가져갈 수 있는 최대 보석의 개수를 출력

접근법

• 탑다운 DP + 비트마스킹으로 접근
• 이전에 어떤 보석을 선택했는지에 따라 다음 선택이 달라질 수 있어 selected에 비트마스크로 선택한 보석 상태를 기록
• 보석을 선택한 경우와 선택하지 않은 경우 두 가지로 나누고,
  • 선택한 경우에는 현재까지 가방에 담긴 보석의 합이 가방 무게를 초과하면 다음 가방에 담는다. → 이때, 주의할 점은 새 가방의 무게가 선택한 보석 무게를 초과하지 않는지도 체크할 것
    • weight는 jewelsi로 갱신, bagCnt+1
  • 현재 가방 무게를 초과하지 않으면 현재 가방에 그대로 담는다.
    • weight는 weight + jewels[i]
  • 보석을 선택할 때마다 (selected | 1 << i(선택한 보석 번호) )로 selected 상태 갱신
• 만약 bagCnt가 전체 가방 개수 M을 초과하면 답이 되지 못하도록 가장 최솟값을 반환 → 가지치기
• 보석 끝까지 조회했다면 return 0; → 기저조건
• dp에 메모이제이션해서 기록했다. → dp[cur][weight][bagCnt][selected]
  • 현재까지(cur) 무게가 wieght고, 가방개수가 bagCnt고 선택한 상태값이 selected일 때 가장 최대로 가져갈 수 있는 보석 개수 저장

코드

import java.io.*;
import java.util.*;


public class Main {
    static int N, M, C;
    static int[] jewels;
    static int[][][][] dp;

    static int recur(int cur, int weight, int bagCnt, int selected) {

        if (bagCnt > M) return Integer.MIN_VALUE;

        if (cur == N) return 0;

        if (dp[cur][weight][bagCnt][selected] != -1) return dp[cur][weight][bagCnt][selected];

        int sum, ret = Integer.MIN_VALUE;
        for (int i = 0; i < N; i++) {

            // 이미 선택한 보석이면 continue;
            if ((selected & 1 << i) != 0) continue;

            sum = weight + jewels[i];

            // 보석을 선택
            if (sum > C && jewels[i] <= C) {
                // 무게합을 가방 무게를 넘어가면서, 현재 보석을 다음 가방에 담을 수 있다면-> bagCnt +1
                ret = Math.max(ret, recur(cur + 1, jewels[i], bagCnt + 1, selected | 1 << i) + 1);
            } else if (sum <= C) {
                // 현재 가방에 담을 수 있다면
                ret = Math.max(ret, recur(cur + 1, sum, bagCnt, selected | 1 << i) + 1);
            }

            // 보석을 선택 X
            ret = Math.max(ret, recur(cur + 1, weight, bagCnt, selected));
        }

        dp[cur][weight][bagCnt][selected] = ret;
        return ret;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        C = Integer.parseInt(st.nextToken());

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

        dp = new int[N + 1][C + 1][M + 1][1 << (N + 1)];
        for (int[][][] d1 : dp) {
            for (int[][] d2 : d1) {
                for (int[] d3 : d2) {
                    Arrays.fill(d3, -1);
                }
            }
        }

        System.out.println(recur(0, 0, 1, 0));
    }
}

 

알고리즘 문제) BOJ 17240. Team Selection

• 링크 : https://www.acmicpc.net/problem/17240

문제 요약

• A, B, C, D, E 총 5개의 역할군이 존재
• 팀의 각 멤버는 서로 다른 역할군을 하나씩 맡음
• 팀을 모집할 때 각 역할군 별로 1명씩 필요한 상황
• 이때 선택할 수 있는 후보자는 총 N명
• 각 후보자별로 역할 군 실력이 ai, bi, ci, di, ei가 주어지면, 0~1000사이 정수
• 이때, 5명의 실력 합이 최대가 되는 팀을 구성할때, 실력 합을 출력

시간 제한

• 1초

입력

• 후보자의 수 N
  • 5 ≤ N ≤ 2만
• 두번쨰 줄부터 N+1번째 줄까지 u번째 후보자의 실력 ai,bi,ci,di,ei가 공백을 두고 주어짐
  • (0 ≤ ai, bi, ci, di, ei ≤ 1,000)

출력

• 역할군의 실력 합이 최대가 되는 팀의 실력 합을 출력

접근법

• 탑다운 dp + 비트마스킹
• 기저조건 : 역할군 5개 모두 선택 또는 후보자를 끝까지 조회했을 경우
• 후보자별로 하나씩 조회하면서 현재 후보를 선택한 경우, 선택하지 않은 경우 2가지로 나눴을 때 반환하는 값을 가장 최댓값으로 갱신
• N이 20000까지 가능하므로 dp배열에 메모이제이션

코드

import java.io.*;
import java.util.*;


public class Main {
    static int N;
    static int[][] arr;
    static int[][] dp;

    static int recur(int cur, int selected) {

        // 역할군 5개를 모두 선택하거나, 후보자들을 모두 둘러봤을 때
        if (selected == (1 << 5) - 1 || cur == N) return 0;

        if (dp[cur][selected] != -1) return dp[cur][selected];

        int ret = 0;
        for (int i = 0; i < 5; i++) {
            if ((selected & 1 << i) != 0) continue;

            // 현재 후보 선택
            ret = Math.max(recur(cur + 1, selected | 1 << i) + arr[i][cur], ret);

            // 현재 후보 선택 X
            ret = Math.max(ret, recur(cur + 1, selected));
        }

        dp[cur][selected] = ret;
        return ret;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        N = Integer.parseInt(br.readLine());

        arr = new int[5][N];
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < 5; j++) {
                arr[j][i] = Integer.parseInt(st.nextToken());
            }
        }

        dp = new int[N + 1][1 << 6];
        for (int[] d : dp) {
            Arrays.fill(d, -1);
        }

        System.out.println(recur(0, 0));

        br.close();
    }
}