[백준/JAVA] 1328번: 고층 빌딩

🔺 문제

1328번: 고층 빌딩

 

 

🔺 코드

import java.util.*;
import java.io.*;
 
public class Main {
    static long mod = 1000000007;
    
    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[][][] D = new long[101][101][101];
        D[1][1][1] = 1;    // 건물이 1개일 때 놓을 수 있는 경우의 수는 1개
        
        for(int i = 2 ; i <= N ; i++) {
            for(int j = 1 ; j <= L ; j++) {
                for(int k = 1 ; k <= R ; k++) {
                    D[i][j][k] = D[i-1][j-1][k] +         // 가장 작은 빌딩을 "왼쪽"에 놓는 경우
                                 D[i-1][j][k-1] +         // 가장 작은 빌딩을 "오른쪽"에 놓는 경우
                                 D[i-1][j][k] * (i - 2);  // 가장 작은 빌딩을 "가운데" 놓는 경우
                    D[i][j][k] %= mod;
                }
            }
        }
        System.out.println(D[N][L][R]);
        br.close();
    }
}

✅ 해결 아이디어
✔ DP- 점화식
- D[N][L][R] : 빌딩 N개를 왼쪽에서 L개, 오른쪽에서 R개가 보이도록 배치할 수 있는 모든 경우의 수

 

💥 유의사항

 ⇨ 이전 경우의 수 계산

• D[ i - 1 ][ j - 1 ][ k ] : 가장 작은 빌딩을 "왼쪽"에 놓는 경우

• D[ i - 1 ][ j ][ k - 1 ] : 가장 작은 빌딩을 "오른쪽"에 놓는 경우

• D[ i - 1 ][ j ][ k ] * ( i  - 2 );  : 가장 작은 빌딩을 "가운데" 놓는 경우

 

---

🔺 다른 풀이들

- 과정 설명이 대박적이다..... 이거다...

[백준 1328번] 고층 빌딩 (java)

[BOJ] 백준 1328 고층빌딩

---

💬 느낀 점

코드는 짧고 간단한 듯한... 하지만

아직까지 제 두뇌는... 해결 아이디어를 찾기까지 도달하지 못 합니다...ㅋㅠ

 

 

1회독	2회독	3회독	4회독	5회독
V	7/7

---

(참고)

✔ Do it 알고리즘 코딩테스트 자바편

✔ 3차원 배열...

java 1차원,2차원,3차원 배열 예제, 배열주소값 복사