백준 - 팔굽혀펴기(10564)

오늘 풀어볼 문제는 ⭐팔굽혀펴기(10564)⭐이다.

1. 문제요약

• 팀의 ⭐⭐누적 득점⭐⭐에 따라 팔굽혀펴기 횟수가 정해진다.
• 최종 팔굽혀펴기 횟수를 보고 팀이 얻을 수 있는 최대 득점 점수를 구하라.

2. 입출력

[입력]

• 테스트 케이스의 개수(1<=T<=20)
• 팔굽혀펴기 횟수 N(1<=N<=5000), 득점의 종류 M (1<=M<=10)
• 팀의 한 번으로 득점 가능한 점수

[출력]

• 팀의 최대 득점 가능 점수
• 불가능하다면 -1 출력

3. 알고리즘

해당 문제는 dp를 활용해야 한다.
이 문제는 팔굽혀펴기의 횟수를 모두 채울때까지, 몇 번이고 득점을 할 수 있다.

팔굽혀펴기카운팅 변수를 pushUpCnt, 득점한 횟수를 turn이라는 변수로 정의하겠다.

turn이란 변수가 왜 굳이 필요할까?

해당 문제의 아주아주아주 중요한 요점은 바로 누적합 계산이란 것이다.
만약 팀이 7점, 3점, 2점 순으로 득점했다면, 동현이는 다음과 같이 푸쉬업을 해야 한다.

[푸쉬업 카운트 하는 법]

• 7점 획득 -> 7회
• 3점 획득 -> 7회(이전 푸쉬업수) + 3회 (현재 득점에 대한 푸쉬업수)
• 2점 획득 -> 10회(이전 푸쉬업수) + 2회(현재 득점에 대한 푸쉬업수)

=> 총 29회!

만약 현재 득점을 1점으로 고정한다고 가정해보자.

그렇다면?

[득점 1점으로 고정]

• 1점 획득 -> 1회
• 1점 획득 -> 1회(이전 푸쉬업수) + 1회 (현재 득점에 대한 푸쉬업수)
• 1점 획득 -> 2회(이전 푸쉬업수) + 1회(현재 득점에 대한 푸쉬업수)

즉 현재 pushUp의 수 = turn * score 라는 공식을 얻을 수 있다!

이제 우린 등차수열 공식이 보이는 것도 발견할 수 있다.
우리의 최대 pushUp 수는 5000이었다. 그렇다면

[최대 turn 수 구하기]

• T (T - 1) / 2 score = 5000
• T (T - 1) / 2 1 = 5000
• T (T - 1) = 10000
  -> T는 약 100

즉, 위 수식에 따라 최대 턴 횟수는 100이 된다

그렇다면 이제 dp 배열을 정의할 수 있다!!!

[DP 배열 정의하기]

• DP[pushUpCnt][turn]
  : i 번째 푸쉬업과 j 번의 turn을 가진다면, value 만큼의 점수를 얻는다!!!

4. 코드

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

public class Main {
    static int INF = (int) -1e9;
    static int N, M;
    static int[] arr;
    static int[][] dp;

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

        int TC = Integer.parseInt(br.readLine());
        while (TC-- > 0) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            N = Integer.parseInt(st.nextToken());
            M = Integer.parseInt(st.nextToken());

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

            dp = new int[N + 1][101];
            for (int i = 0; i <= N; i++) {
                Arrays.fill(dp[i], INF);
            }

            int answer = dfs(N, 1);
            System.out.println(answer > 0 ? answer : -1);
        }
    }
    
    static int dfs(int pushUpCnt, int turn) {
        if (pushUpCnt < 0) return INF;
        if (pushUpCnt == 0) return 0;

        if (dp[pushUpCnt][turn] != INF) return dp[pushUpCnt][turn];

        int result = INF;
        for (int val : arr) {
            int temp = dfs(pushUpCnt - turn * val, turn + 1);
            result = Math.max(result, temp + val);
        }

        dp[pushUpCnt][turn] = result;
        return result;
    }
}