[JAVA] 백준 1328 고층 빌딩

 

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

 

문제분석

플레티넘 난이도의 DP문제를 푸는건 옳지 않을수도 있겠다는 생각이 들었다. 혼자 힘으로 100프로 풀지 못하면 의미가 있나 생각이 든다.

처음에 dp를 2차원 배열로, dp[왼쪽에서 보이는 빌딩 수][오른쪽에서 보이는 빌딩 수] 로 나아가봤다. 하지만 건물 갯수가 많아도 dp[2][2]일 수 있고, 적어도 [2][2]일 수 있다. 나는 i-1개의 건물 갯수에서 i개 건물 갯수 경우의 수로 나아갈 수 있는 공통해를 찾는 데 실패해서, 다른 블로그를 참고해 문제를 풀었다. 아직 내가 풀기엔 너무 어려운 문제라고 생각한다.

 

https://davincicoding.co.kr/130

[백준 1328] 고층 빌딩

 

코드

dp[i][i][1]과 dp[i][1][i]는 크기순으로 정렬된 건물을 상상하면 된다. 경우의 수는 1개밖에 안되기에, 미리 초기화시켜놓는다.

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

public class Main {
    public static void main(String[] args)throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int N = Integer.parseInt(st.nextToken());
        int L = Integer.parseInt(st.nextToken());
        int R = Integer.parseInt(st.nextToken());
        long[][][] dp = new long[101][101][101]; // 저장하는 값은 경우의 수

            dp[1][1][1]=1;
        for(int i = 2; i<N+1; i++){
            dp[i][i][1]=1;
            dp[i][1][i]=1;
            for(int j = 1; j<L+1; j++){
                for(int k = 1; k<R+1; k++){
                    dp[i][j][k] = (dp[i-1][j][k]*(i-2) + dp[i-1][j-1][k] + dp[i-1][j][k-1])%1000000007;
                }
            }
        }
        System.out.println(dp[N][L][R]);
    }
}