세 개의 정수 n, m, k가 주어졌을 때, 다음은 양의 정수로 이루어진 배열에서 최댓값을 찾는 알고리즘입니다.
max_val := -1
max_ind := -1
search_cost := 0
n := size of arr
for initialize i := 0, when i < n, update (increase i by 1), do:
if max_val < arr[i], then:
max_val := arr[i]
max_ind := i
(increase search_cost by 1)
return max_ind우리는 아래 조건을 모두 만족하는 배열 arr을 만들어야 합니다.
- arr은 정확히 n개의 정수를 포함해야 합니다.
- 모든 원소 arr[i]는 1 이상 m 이하의 범위(경계값 포함)에 있어야 합니다. (0 <= i < n)
- 위 알고리즘을 arr에 적용했을 때 search_cost의 값이 정확히 k가 되어야 합니다.
주어진 조건을 만족하도록 배열 arr을 구성하는 방법의 수를 구해야 하며, 답은 매우 커질 수 있으므로 10^9 + 7로 나눈 나머지를 계산합니다.
예를 들어 입력이 n = 2, m = 3, k = 1이라면 정답은 6입니다. 가능한 배열은 [1, 1], [2, 1], [2, 2], [3, 1], [3, 2], [3, 3] 입니다.
접근 방법: 동적 계획법(DP)
이 문제는 메모이제이션을 활용한 동적 계획법으로 효율적으로 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.
- 배열을 왼쪽부터 한 칸씩 채워 나가며, 현재까지의 최댓값(currVal)과 남은 검색 비용(k)을 상태로 관리합니다.
- 새로 넣는 값이 현재 최댓값보다 크면 search_cost가 1 증가하고, 그렇지 않으면 그대로 유지됩니다.
- 모든 위치를 채웠을 때 k가 정확히 0이면 유효한 배열 하나를 찾은 것입니다.
이를 바탕으로 해결 단계는 다음과 같습니다.
- MOD := 10^9 + 7로 설정합니다.
- 두 수를 더한 뒤 MOD로 나눈 나머지를 반환하는 add(a, b) 함수를 정의합니다. 즉 ((a mod MOD) + (b mod MOD)) mod MOD를 반환합니다.
- 메모이제이션을 위한 3차원 배열 dp[54][54][105]를 선언하고 모든 값을 -1로 초기화합니다.
- help(idx, m, k, currVal, n) 함수를 다음과 같이 정의합니다.
- k < 0이면 0을 반환합니다.
- idx == n + 1이면 k == 0일 때 true(1), 아니면 false(0)를 반환합니다.
- dp[idx][k][currVal + 1]이 -1이 아니라면 이미 계산된 값이므로 그대로 반환합니다.
- ret := 0으로 초기화한 뒤, i를 1부터 m까지 순회하며 다음을 수행합니다.
- i > currVal이면 새로운 최댓값이 등장한 것이므로 help(idx + 1, m, k - 1, max(currVal, i), n)의 결과를 ret에 더합니다.
- 그렇지 않으면 help(idx + 1, m, k, max(currVal, i), n)의 결과를 ret에 더합니다.
- 결과를 dp[idx][k][currVal + 1]에 저장한 후 반환합니다.
- 메인 함수에서는 dp 배열을 -1로 초기화한 뒤 help(1, m, k, -1, n)을 호출하여 최종 결과를 반환합니다.
구현 예제
더 나은 이해를 돕기 위해 C++ 전체 구현 코드를 살펴보겠습니다.
#include <bits/stdc++.h>
using namespace std;
typedef long long int lli;
const lli m = 1e9 + 7;
class Solution {
public:
lli add(lli a, lli b) {
return ((a % m) + (b % m)) % m;
}
int dp[54][54][105];
int help(int idx, int m, int k, int currVal, int n) {
if (k < 0)
return 0;
if (idx == n + 1) {
return k == 0;
}
if (dp[idx][k][currVal + 1] != -1)
return dp[idx][k][currVal + 1];
int ret = 0;
for (int i = 1; i <= m; i++) {
if (i > currVal) {
ret = add(help(idx + 1, m, k - 1, max(currVal, i), n), ret);
}
else {
ret = add(help(idx + 1, m, k, max(currVal, i), n), ret);
}
}
return dp[idx][k][currVal + 1] = ret;
}
int numOfArrays(int n, int m, int k) {
for (int i = 0; i < 54; i++)
for (int j = 0; j < 54; j++)
for (int k = 0; k < 105; k++)
dp[i][j][k] = -1;
int ret = help(1, m, k, -1, n);
return ret;
}
};
main() {
Solution ob;
cout << (ob.numOfArrays(2, 3, 1));
}입력
2, 3, 1
출력
6
이 풀이의 상태 공간은 위치(idx), 남은 비용(k), 현재 최댓값(currVal)의 조합이며, 각 상태마다 m번의 분기를 수행하므로 전체 시간 복잡도는 대략 O(n × m² × k)입니다. 메모이제이션 덕분에 동일한 상태를 반복해서 계산하지 않으므로 제약 조건(n, m, k ≤ 50) 내에서 충분히 빠르게 동작합니다.