[BaekJoon] 10564 팔굽혀펴기 (Java)

1.  문제 링크

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

2.  문제

3.  소스코드

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

public class Main {
    static StringBuilder answer = new StringBuilder();
    static Reader scanner = new Reader();

    static int pushupCount;
    static int scoreTypeCount;
    static int[] scores;
    static int[][] dp;

    static void input() {
        pushupCount = scanner.nextInt();
        scoreTypeCount = scanner.nextInt();
        scores = new int[scoreTypeCount];

        for (int idx = 0; idx < scoreTypeCount; idx++) {
            scores[idx] = scanner.nextInt();
        }

        dp = new int[pushupCount + 1][101];
        for (int row = 0; row < dp.length; row++) {
            Arrays.fill(dp[row], -1);
        }
    }

    /*
     * dp[pushupCnt][turn] = pushupCnt번만큼 팔굽혀펴기를 하고 끝에서부터 turn번째 턴일 때의 얻을 수 있는 최대 점수
     *
     * 팔굽혀펴기 개수를 만족하기 위해 필요한 전체 턴을 T, x번째 턴에 획득하는 점수를 score[x]라고 하자
     * 이때, 전체 팔굽혀펴기 횟수는 T * scores[1] + (T - 1) * scores[2] + ... + scores[T]이다
     *  - 팔굽혀펴기 횟수는 몇 번째 차례에 어떤 점수를 득점했는가에 따라 달라진다
     *
     * 우선 최악의 경우를 생각해보자
     *  - 팔굽혀펴기 횟수가 최대이면서 모든 차례에 같은 점수를 득점하는데 이 점수가 최소값이라면 필요한 횟수는 다음과 같다
     *      - T * (T - 1) / 2 * score = 5000
     *      - T * (T - 1) / 2 * 1 = 5000
     *      - T * (T - 1) = 10000
     *      -> T는 약 100
     *  - 즉, 위 수식에 따라 최대 턴 횟수는 100이 된다
     *
     * 턴을 끝을 기준으로 세는 이유
     *  - 처음을 기준으로 세면 정확한 전체 턴 수를 알아야 한다
     *  - 그러나 전체 턴 수는 어떤 점수를 어떤 순서로 선택하느냐에 따라 달라지기 때문에
     *    현재 scores[x]점을 득점해도 전체 팔굽혀펴기 횟수로 가기 위한 현재 턴이 몇 번째인지의 가짓수가 여러가지가 된다
     *  - 즉, 전체 팔굽혀펴기 횟수를 구하는 위 수식에서 scores[x] 앞에 곱하는 T 부분에 들어가는 수가 얼마인지 알 수 없다
     *  - 그러므로 끝을 기준으로 센다
     *
     * 마지막에 얻은 점수는 scores[T]이므로 마지막 바로 전까지 팔굽혀펴기의 횟수는
     *  T * scores[1] + (T - 1) * scores[2] + ... + 2 * scores[T - 1]이 되고
     * 마지막에서 두 번째 얻은 점수는 2 * scores[T - 1]이므로 마지막에서 세 번째 팔굽혀펴기의 횟수는
     *  T * scores[1] + (T - 1) * scores[2] + ... + 3 * scores[T - 2]가 된다
     *
     * 위 수식을 통해 아래와 같은 점화식을 구할 수 있다
     *  dp[pushupCnt][turn] = max(dp[pushupCnt][turn], dp[pushupCnt - turn * scores[idx]][turn + 1] + scores[idx])
     */
    static void solution() {
        int maxPoint = findMaxPoint(pushupCount, 1);
        if (maxPoint <= 0) {
            answer.append(-1).append('\n');
            return;
        }
        answer.append(maxPoint).append('\n');
    }

    static int findMaxPoint(int count, int turn) {
        if (count == 0) {
            return 0;
        }
        if (dp[count][turn] != -1) {
            return dp[count][turn];
        }

        dp[count][turn] = Integer.MIN_VALUE;
        for (int score = 0; score < scoreTypeCount; score++) {
            if (count - (turn * scores[score]) >= 0) {
                dp[count][turn] = Math.max(dp[count][turn],
                        findMaxPoint(count - (turn * scores[score]), turn + 1) + scores[score]);
            }
        }

        return dp[count][turn];
    }

    public static void main(String[] args) {
        int T = scanner.nextInt();
        for (int test = 0; test < T; test++) {
            input();
            solution();
        }

        System.out.print(answer);
    }

    static class Reader {
        BufferedReader br;
        StringTokenizer st;

        public Reader() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        String next() {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }

            return st.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }
    }
}