[LeetCode] 1420. Build Array Where You Can Find The Maximum Exactly K Comparisons

https://leetcode.com/problems/build-array-where-you-can-find-the-maximum-exactly-k-comparisons/description/

LeetCode - The World's Leading Online Programming Learning Platform

문제 유형 : 배열 / 다이나믹 프로그래밍

문제 난이도 : Hard

 

문제

You are given three integers n, m and k. Consider the following algorithm to find the maximum element of an array of positive integers:

You should build the array arr which has the following properties:

• arr has exactly n integers.
• 1 <= arr[i] <= m where (0 <= i < n).
• After applying the mentioned algorithm to arr, the value search_cost is equal to k.

Return the number of ways to build the array arr under the mentioned conditions. As the answer may grow large, the answer must be computed modulo 10^9 + 7.

 

조건에 맞는 배열의 개수를 구하시오.

 n : 배열의 길이

m : 요소가 가질 수 있는 최대의 값

k : 배열 순회 중 최댓값이 갱신되는 횟수

 

풀이

dp[i][maxNum][cost]를 아래의 두 경우로 나누어 정의합니다:

1. 배열에 추가된 마지막 숫자가 새로운 최댓값이 아닌 경우:
   • 이 경우, 마지막 숫자는 1부터 maxNum까지의 범위에서 올 수 있으며, 비용은 변경되지 않습니다.
2. 배열에 추가된 마지막 숫자가 새로운 최댓값인 경우:
   • 이 경우, 이전 최댓값은 1부터 maxNum - 1까지의 범위에서 올 수 있으며, 비용은 1 감소합니다.

그러나 각 상태에서 가능한 최댓값들에 대한 합을 계산하면 비효율적이므로, 최적화를 위해 각 비용에 대한 현재 최댓값까지의 유효한 배열의 합을 추적하는 접두사 합 배열을 도입합니다. 이렇게 하면 효율적으로 상태를 갱신할 수 있습니다.

 

코드

C++

class Solution {
public:
    int numOfArrays(int n, int m, int k) {
        ios_base::sync_with_stdio(false);
        cin.tie(nullptr);
        cout.tie(nullptr);

        if(m<k)return 0;
        int dp[2][m+1][k+1],mod=1e9+7;
        memset(dp,0,sizeof(dp));
        for(int j=1;j<=m;++j)
            dp[0][j][1]=j;
        for(int i=1;i<n;++i)
            for(int j=1;j<=m;++j)
                for(int l=1;l<=min(i+1,min(j,k));++l)
                    dp[i&1][j][l]=(dp[i&1][j-1][l]+(long)(dp[(i-1)&1][j][l]-dp[(i-1)&1][j-1][l])*j+dp[(i-1)&1][j-1][l-1])%mod;
        return (dp[(n-1)&1][m][k]+mod)%mod;
    }
};