백준 6506 (엘 도라도) - java

문제

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

 

상근이는 라스베가스의 엘 도라도 카지노에 도착했다. 태어나서 카지노에 처음 가본 상근이는 휘황찬란한 카지노의 내부에 입을 다물 수 없었다. 그런 그의 눈길을 사로 잡는 게임이 하나있었다. 그 게임은 화면에 n개의 숫자가 화면에 뜨는 아주 단순해 보이는 게임이었다. 이 게임의 참가자는 컴퓨터가 만드는 수열에서 길이가 k인 증가하는 부분 수열의 개수를 예상해야 한다.

수열 a1, ..., an의 부분 수열은 1 ≤ i1 < i2 < ... < il ≤ n를 만족하는 ai1, ..., ail로 정의 한다. 부분 수열이 증가하려면 모든 1 < j ≤ l에 대해서, aij-1 < aij를 만족해야 한다.

상근이는 다른 사람이 작성한 프로그램을 믿지 않는다. 따라서, 기계에 표시된 정답 대신 자신이 직접 정답을 구해 보려고 한다. 기계의 화면에 표시된 숫자가 주어졌을 때, 길이가 k이면서 증가하는 부분 수열의 개수를 세는 프로그램을 작성하시오.

 

유형 : DP

 

접근 방식

• LIS 문제를 응용하는 DP 문제이다. 문제를 해결하기 위해서는 DP[N][K]로 배열을 만들고 다음과 같이 접근해야 한다.
• DP[N][K] = Sum(DP[1 ~ N -1][K-1])
  • 정말 간단한 점화식이다. 수열이라는 의미 자체가 증가가 중요하지 연속성은 따지는 개념이 아니다.

전체 코드

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

public class Main {

    static int n,k;
    static int[] board = new int[101];
    static long[][] dp = new long[101][101];

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

        while (true) {
            st = new StringTokenizer(br.readLine()," ");

            n = Integer.parseInt(st.nextToken());
            k = Integer.parseInt(st.nextToken());

            if(n == 0 && k == 0)
                break;

            st = new StringTokenizer(br.readLine()," ");
            for(int i = 1 ; i <= n ; i++) {
                board[i] = Integer.parseInt(st.nextToken());
            }

            init();

            for(int i = 2 ; i <= n ; i++) {
                for(int j = i - 1 ; j >= 1 ; j--) {

                    if(board[i] <= board[j])
                        continue;

                    for(int a = 2 ; a <= k ; a++) {
                        dp[i][a] += dp[j][a-1];
                    }
                }
            }

            long result = 0;

            for(int i = 1 ; i <= n ; i++) {
                result += dp[i][k];
            }

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

        System.out.print(sb);

        br.close();
    }

    static void init() {
        for(int i = 1 ; i <= n ; i++) {
            for(int j = 1 ; j <= k ; j++) {
                dp[i][j] = 0;
            }

            dp[i][1] = 1;
        }
    }
}