[Algo] 백준 28071 승형이의 사탕 사기 JAVA

문제 바로가기 : https://www.acmicpc.net/problem/28071

---

코드

bfs

메모리 : 22780KB

시간 : 336ms

언어 : Java 11

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

public class Main {
    static class Node {
        int num, depth;

        Node(int num, int depth) {
            this.num = num;
            this.depth = depth;
        }
    }

    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(st.nextToken());
        int[] candy = new int[N];
        st = new StringTokenizer(br.readLine());
        Queue<Node> q = new LinkedList<>();
        int maxcandy = 0;
        for (int i = 0; i < N; i++) {
            candy[i] = Integer.parseInt(st.nextToken());
            q.add(new Node(candy[i], 1));
            maxcandy = Math.max(maxcandy, candy[i]);
        }
        int max = 0;
        boolean[] check = new boolean[maxcandy * M + 1];
        while (!q.isEmpty()) {
            Node n = q.poll();
            if (n.num % K == 0) {
                max = Math.max(max, n.num);
            }
            if (n.depth == M) {
                continue;
            }
            for (int i = 0; i < N; i++) {
                if (!check[n.num + candy[i]]) {
                    check[n.num + candy[i]] = true;
                    q.add(new Node(n.num + candy[i], n.depth + 1));
                }
            }
        }
        System.out.println(max);
    }
}

풀이

승형이의 사탕 사는 조합을 bfs로 구할 수 있다.
승형이가 살 수 있는 사탕의 최대 개수는 (최대상자*상자에 들어 있을 수 있는 최대 사탕 수) 이다.
따라서 bfs를 돌면서 K로 나눠지는 경우를 모두 찾아서 최댓값을 찾으면 된다.

---

코드

배낭 알고리즘(DP)

메모리 : 15640KB

시간 : 424ms

언어 : Java 11

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

public class Main {
    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(st.nextToken());
        int[] candy = new int[N];
        st = new StringTokenizer(br.readLine());
        int[][] dp = new int[M + 1][K];
        for (int i = 0; i < N; i++) {
            candy[i] = Integer.parseInt(st.nextToken());
            dp[1][candy[i] % K] = Math.max(candy[i], dp[1][candy[i] % K]);
        }

        int ans = 0;
        for (int i = 1; i < M; i++) {
            for (int j = 0; j < N; j++) {
                for (int k = 0; k < K; k++) {
                    if (dp[i][Math.floorMod(k - candy[j], K)] != 0) {
                        dp[i + 1][k] = Math.max(dp[i + 1][k], dp[i][Math.floorMod(k - candy[j], K)] + candy[j]);
                    }
                }
            }
        }
        for (int i = 0; i <= M; i++) {
            // 나머지가 0인것 중 가장 큰 것
            ans = Math.max(dp[i][0], ans);
        }
        System.out.println(ans);
    }
}

풀이

너무너무..어려웠다 DP는 어려워ㅠ
K로 나눠지는 수 만큼의 사탕을 가져야 한다는 것을 나머지를 이용해 해결했다.

나머지가 K-n인 사탕과 나머지가 n인 사탕을 더하면 결국 K의 배수가 된다
이 아이디어를 이용해 점화식을 세우면 다음과 같다

    for (int i = 1; i < M; i++) {
            for (int j = 0; j < N; j++) {
                for (int k = 0; k < K; k++) {
                    // 나머지를 맞출 짝이 없다면 넘겨야 한다.
                    if (dp[i][Math.floorMod(k - candy[j], K)] != 0) {
                        //i개의 사탕상자를 샀을 때 k개의 나머지가 나오는 경우는 =
                        //전에 기억했던 값, (현재의 찾을 나머지 k - 지금 산 사탕상자)%K + 지금 산 사탕상자   중 큰 값
                        dp[i + 1][k] = Math.max(dp[i + 1][k], dp[i][Math.floorMod(k - candy[j], K)] + candy[j]);
                    }
                }
            }
        }

dp[i][Math.floorMod(k - candy[j], K)] 에서 Math.floorMod(k - candy[j], K) 는 현재 산 candy[i] 와 짝을 지을 전 칸의 나머지를 찾는 것이다.
dp배열을 완성하고 나면 나머지가 0인 것들 중에서 최댓값을 찾아주면 된다.