[백준] 6506: 엘 도라도 - JAVA

07 Sep 2023 in Algorithm on 다이나믹 프로그래밍

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

풀이

n개의 숫자로 이루어진 배열에서 k개의 숫자로 만들 수 있는 증가하는 부분 수열의 개수를 구해야한다.

dp배열을 long[n][k + 1] 로 만들었다.

dp[i][j]가 의미하는 것은

arr[i]를 포함하여 인덱스가 i보다 큰 j-1개의 숫자들과 j길이의 증가하는 부분 수열의 개수이다.

즉, dp[i][j]를 구하기 위해서는 다음과 같은 코드를 이용한다.

long tmp = 0;
for (int x = i + 1; x < n; x++) {
    if (arr[x] > arr[idx]) {
        tmp += solve(x, j - 1);
    }
}
dp[i][j] = tmp;

이렇게 되면 i인덱스와 그 이상의 숫자를 포함한 j길이의 증가하는 부분수열의 개수가 구해진다.

따라서, n개의 숫자, k의 길이라고 할 때 1부터 n-1까지 dp[i][k]의 값을 더해주면 정답이 된다.

---

메모리: 15860KB

시간: 168ms

언어: Java 11

코드

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

public class Main {
    static int n, k;
    static int[] arr;
    static long[][] dp;

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

        StringBuilder sb = new StringBuilder();
        while (true) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            n = Integer.parseInt(st.nextToken());
            k = Integer.parseInt(st.nextToken());
            if (n == 0 && k == 0) {
                break;
            }

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

            dp = new long[n][k + 1];
            for (int i = 0; i < n; i++) {
                Arrays.fill(dp[i], -1);
                dp[i][1] = 1;
            }

            long ans = 0;
            for (int i = 0; i < n; i++) {
                ans += solve(i, k);
            }

            sb.append(ans).append("\n");
        }

        System.out.println(sb);
    }

    private static long solve(int idx, int len) {
        if (dp[idx][len] != -1) {
            return dp[idx][len];
        }

        long tmp = 0;
        for (int i = idx + 1; i < n; i++) {
            if (arr[i] > arr[idx]) {
                tmp += solve(i, len - 1);
            }
        }

        return dp[idx][len] = tmp;
    }

}