문제 링크
문제
티어: 골드 2
알고리즘: dp
입력
첫째 줄에 N, M, K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ M ≤ 220, 1 ≤ K ≤ 2147483647)
출력
합이 M인 길이가 N인 수열 중 K번째 수열을 출력한다. 항상 답이 존재 하는 경우만 입력으로 주어진다.
풀이
합이 M인 길이가 N인 수열 중 K번째 수열을 출력해야 한다.
K는 최대 2147483647이기 때문에 사전 순 1번 부터 K번까지 직접 구하는건 불가능하다.
그러면 중복된 부분을 한 번만 계산하는 dp를 생각할 수 있다.
중복된 부분을 찾기 위해서 예제 입력 1를 이용해 보겠다.
4 9 3x x x x
오른쪽에서 세 번째 자리가 1일 때 세 번재 자리 + 두 번재 자리 + 첫 번째 자리의 합이 8인 값을 찾으려면 두 번째 자리 + 첫 번재 자리가 7이어야 한다.
그리고 두 번째 자리 + 첫 번째 자리가 7인 값은 네 번째 자리든, 다섯 번째 자리든 언제든 재사용될 수 있는 값이다.
이걸 매번 구하는 것은 당연히 비효율적이다.
그래서 메모제이션을 활용해야 한다.
두 번째 자리에서는 첫 번째 자리의 가능한 모든 합이 필요하고,
세 번째 자리에서는 두 번째 자리 + 첫 번째 자리의 가능한 모든 합이 필요하다.
또한 세 번째 자리 값이 결정되면, 두 번째 자리와 첫 번째 자리는 이 값보다 같거나 큰 값이어야 한다.
그래서 dp를 다음과 같이 정의해 줄 수 있다.
dp[A][B][C]
- A는 몇 번째 자리인지
- B는 그 자리의 수가 몇 인지
- C는 합
만약 dp[3][2][8]이면 세 번째 자리 + 두 번째 자리 + 첫 번째 자리의 합이 8이면서 두 번재 자리와 첫 번째 자리의 수가 2보다 같거나 큰 모든 경우의 수를 뜻한다.
그래서 dp[3][2][8]은 다음과 같이 구할 수 있다.
두 번째 자리와 첫 번째 자리의 합이 8 - 2 = 6인 값을 구해야 한다.
그러나 2보다 크거나 같아야 한다.
dp[2][2][6] ~ dp[2][9][6]까지 더한 값이 dp[3][2][8]이 된다.
이렇게 dp[N][220][220]까지 구하고, 이제 K번 째 수열을 구해야 한다.
N번 째 자리부터 보자
N번 째 자리가 1이면서 합이 M인 -> dp[N][1][M]는 조건을 만족하는 1 x x x의 모든 경우의 수다.
만약 이 값이 K보다 작다면 아직 해당 자리에 값을 결정해 줄 수 없다.
N번째 자리가 2면서 합이 M인 경우 dp[N][2][M]은 조건을 만족하는 2 x x x의 모든 경우의 수다.
전에 값과 이 값을 더한 값이(1 x x x + 2 x x x) K보다 크다면 해당 자리 수를 2로 결정할 수 있다. 왜냐하면 1 x x x보다 크고 2 x x x의 마지막 값보다 작기 때문이다.
그리고 다음 N - 1번째 자리의 수를 구해야 하는데 이때 K와 M의 업데이트가 필요하다. N번 째 자리를 구하는 과정에서 1 x x x는 아니며 2로 결정 됐기 때문에 K = K - (1 x x x의 경우의 수)다. 또한 M = M - 2이며, N - 1 번째 자리 수는 2보다 크거나 같아야 한다. N번 째 자리가 2이기 때문이다.
이렇게 M과 K를 업데이트 해주고, N번 째 자리 수보다 같거나 큰 값부터 똑같이 반복해 주면 원하는 수열을 구할 수 있다. 2 x x -> 3 x x -> 4 x x
이 풀이의 시간 복잡도는 O(N M M)이다.
소스 코드
import java.io.*;
import java.util.*;
public class Main {
static int N, M, K;
public static void main(String args[]) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
K = Integer.parseInt(st.nextToken());
long[][][] dp = new long[N + 1][221][221]; // [A][B][C] -> A는 몇 번째 자리인지, B는 수, C는 합
for(int i=1; i<=220; i++) {
dp[1][i][i] = 1;
}
for(int i=2; i<=N; i++) {
for(int j=1; j<=220; j++) {
for(int k=2; k<=220; k++) {
dp[i][j][k] = find(i - 1, j, k - j, dp);
}
}
}
StringBuilder sb = new StringBuilder();
int nextNum = 1;
for(int i=N; i>=1; i--) {
long sum = 0;
for(int j=nextNum; j<=220; j++) {
sum += dp[i][j][M];
if(sum >= K) {
sb.append(j).append(" ");
K -= (sum - dp[i][j][M]);
M -= j;
nextNum = j;
break;
}
}
}
System.out.println(sb.toString().trim());
}
static long find(int s, int num, int value, long[][][] dp) {
if(value <= 0 ) {
return 0;
}
long rv = 0;
for(int i = num; i<=220; i++) {
if(dp[s][i][value] > 0) {
rv += dp[s][i][value];
}
}
return rv;
}
}