[자바] 백준 1328 : 고층 빌딩 (DP 풀이) 접근 방법 및 풀이

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

1328번: 고층 빌딩

플래티넘5 난이도, 정답률 34% 문제입니다.

---

문제 풀이

문제를 풀기 위해서는 이 문제의 의도를 먼저 이해해야합니다.

​

N개의 빌딩이 있고, 왼쪽에서 봤을 때 보이는 빌딩의 수는 L개, 오른쪽에서 봤을 때 보이는 빌딩의 수는 R개입니다.

​

N, L, R의 값이 주어졌을 때 가능한 빌딩 순서의 경우의 수를 찾으면 됩니다.

​

말이 조금 어려울 수 있지만 문제에서 주어진 예시로 한 번 봐보겠습니다.

N = 5, L = 3, R = 2인 경우 빌딩의 수는 5개, 왼쪽에서 보이는 빌딩의 수는 3개, 오른쪽에서 보이는 빌딩의 수는 2개입니다.

​

이 경우 빌딩의 배치가 될 수 있는 예시 하나를 보면 1 3 5 2 4 가 됩니다.

이를 그림으로 표현하면 아래와 같은 순서인 경우 N, L, R에 만족하는 하나의 경우가 됩니다.

 

 

왼쪽에서 본 경우 빌딩은 3개가 보이고, 오른쪽에서 본 경우는 빌딩 2개가 보이죠?

이렇게 가능한 모든 경우를 구해주면 됩니다.

 

문제 풀이 도출 및 접근 방법

처음에는 단순히 완전탐색(dfs) 방식으로 해결하려고 했습니다.

하지만 문제에서 주어지는 조건을 보면 이 방식으로 해결 할 수가 없습니다.

​

문제에서 N(빌딩의 수)의 값은 최대 100개입니다.

이 경우에서 완전탐색을 하기 위해서는 시간복잡도가 엄청 안 좋기 때문에 시간초과가 뜰 것이라고 생각했습니다.

​

또한 문제에서 빌딩의 경우의 수를 1000000007 값으로 나눈 나머지를 출력하는 것이라고 명시되어 있기 때문에 여기서 무조건 다른 풀이로 풀어야 한다고 생각했습니다.

​

그래서 하나하나 경우를 생각하며 값을 직접 내보다가 점화식을 발견해서 저는 DP를 이용해서 해결했습니다.

​

규칙을 파악하고 구한 점화식은 다음과 같습니다.

building[i][j][k] = building[i - 1][j][k - 1] + building[i - 1][j - 1][k] + building[i - 1][j][k] * (i - 2)

​

building[i][j][k]를 만족하는 경우의 수를 구하기 위해서는

1. i-1개의 빌딩에서 왼쪽에서 보이는 빌딩의 수가 같고 오른쪽에서 보이는 빌딩의 수 -1개인 것의 빌딩의 순서를 구해줍니다.
2. i-1개의 빌딩에서 왼쪽에서 보이는 빌딩의 수가 -1개이고, 오른쪽에서 보이는 빌딩의 수가 같은 것의 순서의 개수를 구해줍니다.
3. i-1개의 빌딩에서 왼쪽과 오른쪽에서 보이는 빌딩의 수의 값 * (i-2) 를 해줍니다.
4. 이 값들을 모두 더하면 빌딩의 순서의 개수를 구할 수 있고 이를 주어진 수로 나눈 나머지를 출력하면 됩니다.

 

문제 풀이

 

import java.util.Scanner;

public class Main {
    private static int n, l, r;
    private static long[][][] building;
    private static final long MOD_NUMBER = 1000000007;

    public static void main(String[] args) {
        initDataSet();
        initBuilding();
        countBuildingOrder();
        System.out.println(building[n][l][r]);
    }

    public static void countBuildingOrder() {
        for (int i = 2; i <= n; i++) {
            for (int j = 1; j <= l; j++) {
                for (int k = 1; k <= r; k++) {
                    building[i][j][k] =
                            (building[i - 1][j][k - 1] + building[i - 1][j - 1][k] + building[i - 1][j][k] * (i - 2)) % MOD_NUMBER;
                }
            }
        }
    }

    public static void initBuilding() {
        building = new long[101][101][101];
        building[1][1][1] = 1;
    }

    public static void initDataSet() {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        l = sc.nextInt();
        r = sc.nextInt();
    }
}

​

​사실 저 또한 DP 문제를 많이 풀지 않아서 익숙하지는 않지만, 보통의 경우 저는 완전탐색을 이용해서 풀어야하지만 완전탐색으로 시간초과가 뜨는 경우라면 그리디 혹은 DP를 이용해서 해결합니다.

​

DP 문제를 몇 문제를 풀다보면 DP 안에서도 문제의 유형이 조금씩 나뉘는 것을 확인할 수 있습니다.

1. Math.max를 이용해서 최대값을 갱신해주는 문제
2. 점화식을 이용해서 값을 구해주는 문제

이 문제 같은 경우는 가능한 모든 경우의 수를 찾는 문제이니 2번의 유형이죠? 따라서 점화식을 찾아보면 됩니다.

점화식을 찾지 못한 경우에는 그리디로 해결하시면 됩니다!

​

다른 좋은 방법이 있으면 또 찾아서 풀이를 올리겠습니다.

​