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

15 Jun 2023 in Algorithm on 다이나믹 프로그래밍

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

풀이

dp문제이다.

M개의 사탕 상자를 가져갈 수 있고, 사탕 개수의 총 합은 K로 나누어 떨어져야 한다.

상자의 개수와 나머지에 따라 dp배열을 생성한다.

dp[i][j]에서 i를 상자의 개수, j를 나머지라고 하면

dp[i][j]의 값은 i-1개의 상자에서 “j - 현재 사탕상자의 사탕 개수”일때의 dp값을 이용하여 갱신한다.

“j - 현재 사탕상자의 사탕 개수”가 음수가 되면 안되기 때문에 Math.floorMod연산을 사용했다.

dp배열을 채운 후 나머지가 0인 경우 중 최댓값을 구한다.

---

메모리: 15152KB

시간: 424ms

언어: Java 11

코드

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

public class Main {
    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 M = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(st.nextToken());

        int[] arr = new int[N];
        int[][] dp = new int[M + 1][K];
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
            // 상자를 1개 선택했을 때 dp값을 초기화해준다.
            dp[1][arr[i] % K] = Math.max(dp[1][arr[i] % K], arr[i]);
        }

        for (int i = 2; i < M + 1; i++) {
            for (int j = 0; j < N; j++) {
                for (int k = 0; k < K; k++) {
                    // 상자개수-1일때의 값이 있을 때 현재 값을 갱신한다.
                    if (dp[i - 1][Math.floorMod(k - arr[j], K)] != 0) {
                        // 상자개수-1일때의 값에서 현재 사탕 개수를 더했을 때 나머지가 k가 될 때와 비교해준다.
                        dp[i][k] = Math.max(dp[i][k], dp[i - 1][Math.floorMod(k - arr[j], K)] + arr[j]);
                    }
                }
            }
        }

        int ans = 0;
        // 나머지가 0인 경우 중 최댓값을 찾는다.
        for (int i = 1; i < M + 1; i++) {
            ans = Math.max(dp[i][0], ans);
        }

        System.out.println(ans);
    }

}