#1328 고층 빌딩
난이도 : 골드 1
유형 : DP/ 조합
1328번: 고층 빌딩
상근이가 살고있는 동네에는 빌딩 N개가 한 줄로 세워져 있다. 모든 빌딩의 높이는 1보다 크거나 같고, N보다 작거나 같으며, 같은 높이를 가지는 빌딩은 없다. 상근이는 학교 가는 길에 가장 왼
www.acmicpc.net
▸ 문제
상근이가 살고있는 동네에는 빌딩 N개가 한 줄로 세워져 있다. 모든 빌딩의 높이는 1보다 크거나 같고, N보다 작거나 같으며, 같은 높이를 가지는 빌딩은 없다. 상근이는 학교 가는 길에 가장 왼쪽에 서서 빌딩을 몇 개 볼 수 있는지 보았고, 집에 돌아오는 길에는 가장 오른쪽에 서서 빌딩을 몇 개 볼 수 있는지 보았다.
상근이는 가장 왼쪽과 오른쪽에서만 빌딩을 봤기 때문에, 빌딩이 어떤 순서로 위치해있는지는 알 수가 없다.
빌딩의 개수 N과 가장 왼쪽에서 봤을 때 보이는 빌딩의 수 L, 가장 오른쪽에서 봤을 때 보이는 빌딩의 수 R이 주어졌을 때, 가능한 빌딩 순서의 경우의 수를 구하는 프로그램을 작성하시오.
예를 들어, N = 5, L = 3, R = 2인 경우에 가능한 빌딩의 배치 중 하나는 1 3 5 2 4이다.
▸ 입력
첫째 줄에 빌딩의 개수 N과 가장 왼쪽에서 봤을 때 보이는 빌딩의 수 L, 가장 오른쪽에서 봤을 때 보이는 빌딩의 수 R이 주어진다. (1 ≤ N ≤ 100, 1 ≤ L, R ≤ N)
▸ 출력
첫째 줄에 가능한 빌딩 순서의 경우의 수를 1000000007로 나눈 나머지를 출력한다.
문제 풀이
이 문제는 오히려 Top-down으로 풀어내기가 더 어려운 문제이다. 처음에 자연스레 Top-down으로 접근했다가 오히려 더 고생했다.
조건
1) 빌딩의 개수 1~100개
2) 왼쪽에서 봤을 때 보이는 수 L, 오른쪽에서 보이는 수 R은 1~N
↓ 막힌 풀이
N=1
빌딩 한 개로 L=1, R=1의 경우의 수 1개밖에 없다.
N=2
L=2, R=1 빌딩 [1 2] -> 1개
L=1, R=2 빌딩 [2 1] -> 1개
N=3
L=3, R=1 빌딩 [1 2 3] -> 1개
L=2, R=2 빌딩 [1 3 2] [2 3 1] -> 2개
L=1, R=3 빌딩 [3 2 1] -> 1개
N=4
L=4, R=1 빌딩 [1 2 3 4] -> 1개
L=3, R=2 빌딩 [1 2 4 3] [1 3 4 2] [2 3 4 1] -> 3개
L=2, R=3 빌딩 [3 4 2 1] [1 4 3 2] [2 4 3 1] -> 3개
L=4, R=1 빌딩 [4 3 2 1] -> 1개
빌딩의 수 N이 늘어날 때마다 보면 알겠지만 이전의 N-1의 경우에서 L과 R의 개수에 따라 값이 추가되는 것을 볼 수 있다.
1) L값 증가 : N-1의 빌딩의 수에서 L이 1추가 되려면 N은 왼쪽에서 L번째 인덱스에 추가되면 된다. (1 3 2) -> (1 3 4 2)
ex) N3 L2 R2 -> N4 L3 R2 : (1 3 2) -> (1 3 4 2)
dp[N][L][R] += dp[N-1][L-1][R]
2) R값 증가 : 1)의 반대로 N-1의 빌딩의 수에서 R이 1추가 되려면 N은 오른쪽에서 R번째 인덱스에 추가되면 된다.
ex) N3 L3 R1 -> N4 L3 R2 : (1 2 3) -> (1 2 4 3)
dp[N][L][R] += dp[N-1][L][R-1]
따라서 점화식은 dp[N][L][R] = dp[N-1][L][R-1] + dp[N-1][L-1][R]이다. 단, N=R, L=1 이거나 N=L, R=1일 때는 경우의 수는 오름차순, 내림차순으로 1개밖에 존재하지 않는다.
그런데 이 이후로 그 뒤 풀이가 진행이 되지 않았다...
문제는 L과 R의 수가 자유롭다는 것이다. 기존의 조합문제였다면 L+R값이 N-1또는 N또는 어떤 값이든 고정되어 있었을 것이다. 그러나, 이 문제는 N=5이라고 꼭 L과 R의 값이 빌딩의 수와 맞지 않아도 된다.
* 만약 1 5 4 3 2 라면 N=5, L=2, R=4이다.
그래서 N이 추가될수록 높은 빌딩을 추가해준다면?
빌딩 [1 3 2]에서 각 자리에 4를 추가해보자.
[1 3 2]는 N=3, L=2, R=2
N=4, (L,R) = (1,3) + (2,3) + (3,2) + (4,1)
> [4 1 3 2] [1 4 3 2] [1 3 4 2] [1 3 2 4]
이렇게 되면 점화식을 생각해내기에는 파생되어 나오는 경우의 수가 너무 많다.
그래서 좀 다르게 생각해야하는데 N이 증가할수록 가장 작은 빌딩의 수를 넣어보는 것이다.
(이 부분이 난이도 높은 이유 같다. 생각해내기 어려웠다..)
N값이 증가함에 따라 당연히 증가하는 빌딩의 높이를 넣는게 일반적인 사고인데 이 문제는 사고의 전환이 필요했다.
생각해낼 때 빌딩이라고 고정을 해버려서 이쪽의 사고가 잘 돌아가지 않았던 것 같다. 문제를 빌딩이 아니라 나무로 생각하면 쉽다.
도로에 나무를 심는 곳이 있는데 나무들은 한 달 마다 길이가 1씩 자란다. 그리고 매달 새로운 나무를 심어주는데 심는 위치는 무작위로 심어진다. 새로 심어지는 나무의 길이는 1이다.
이제 다시 빌딩으로 나무로 가정하고 풀이를 시작해보자.
그냥 N+1일이 되면 N개의 각 기존에 있던 값들이 1씩 증가하고 새로운 1이 추가되는 것이다. 조합으로 나온 값은 다음과 같다.
N=1
나무 한 개로 L=1, R=1의 경우의 수 1개밖에 없다.
N=2
L=2, R=1 나무 [1 2] -> 1개
L=1, R=2 나무 [2 1] -> 1개
N=3
L=3, R=1 나무 [1 2 3] -> 1개
L=2, R=2 나무 [1 3 2] [2 3 1] -> 2개
L=1, R=3 나무 [3 2 1] -> 1개
N=4
L=4, R=1 나무 [1 2 3 4] -> 1개
L=3, R=2 나무 [1 2 4 3] [1 3 4 2] [2 3 4 1] -> 3개
L=2, R=3 나무 [3 4 2 1] [1 4 3 2] [2 4 3 1] -> 3개
L=4, R=1 나무 [4 3 2 1] -> 1개
그래서 빌딩의 수가 N일 때 N!의 경우의 수에서 조합은 빼고 다 조사해야 한다. N이 증가할수록 새로운 경우가 생기는데 이는 조합으로 다 표현했다. 그래서 나머지의 경우는 이전에 발생한 경우에 포함되어 있을 것이다.
N=2 (2! =2)
L=2, R=1 나무 [1 2] -> 1개
L=1, R=2 나무 [2 1] -> 1개
N=3 (3! -4 = 2가지)
L=2, R=1 나무 [2 1 3] -> 1개 : dp[2][2][1]
L=1, R=2 나무 [3 1 2] -> 1개 : dp[2][1][2]
N=3까지는 아직 감이 안잡힌다.
N=4 (4! - 8 = 16개)
L=3, R=1 나무 [1 3 2 4] [2 1 3 4] [2 3 1 4] -> 3개 : dp[3][2][1] + dp[3][3][1]*2 + dp[3][3][0]
L=2, R=1 나무 [3 1 2 4] [3 2 1 4] -> 2개 : dp[3][1][1] + dp[3][2][1] *2 + dp[3][2][0]
L=2, R=2 나무 [3 2 4 1] [2 1 4 3] [2 4 1 3] [3 4 1 2] [3 1 4 2] [1 4 2 3] -> 6개
: dp[3][2][1] + dp[3][2][2] *2 + dp[3][1][2]
...
이렇게 보면 점화식이 나온 것 같다.
- 가장 왼쪽에 나무가 자란다면 추가하면 L이 증가한다. dp[N][L][R] += dp[N-1][L-1][R]
- 가장 오른쪽에 나무가 자란다면 추가하면 R이 증가한다. dp[N][L][R] += dp[N-1][L][R-1]
- 가장 왼쪽과 오른쪽을 제외한 그 사이에 나무가 자란다면 L과 R값은 변하지 않는다. dp[N][L][R] += dp[N-1][L][R] * (N-2)
(* N-2는 나무 사이 공간 개수)
☛ dp[N][L][R] = dp[N-1][L-1][R]+ dp[N-1][L][R-1] + dp[N-1][L][R] * (N-2)
그림으로 보면 더 이해하기 쉽다.
점화식 코드
static void solve(int n, int l, int r) {
dp[1][1][1] = 1;
for (int i = 2; i< n+1; i++) {
dp[i][i][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-1] +dp[i - 1][j - 1][k]
+ (dp[i - 1][j][k] * (i-2)))%div;
}
}
}
}
풀이 코드
읽어도 이해가 안가면 직접 손으로 쓰면서 풀이해보는 것을 추천한다. 풀이코드만 보면 되게 간단한 문제인 것 같지만 결코 쉽다고 생각하지 않는다. 앞으로 문제를 기계적이 아닌 유연한 사고로 다가는 법을 신경써서 길러야겠다
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
static long[][][] dp;
static int div = 1000000007;
public static void main(String[] args) throws Exception{
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());
dp = new long[n+1][n+1][n+1];
solve(n,l,r);
System.out.println(dp[n][l][r]);
}
static void solve(int n, int l, int r) {
dp[1][1][1] = 1;
for (int i = 2;i< n+1; i++) {
dp[i][i][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-1] +dp[i - 1][j - 1][k]
+ (dp[i - 1][j][k] * (i-2)))%div;
}
}
}
}
}
'Dot Algo∙ DS > PS' 카테고리의 다른 글
| [BOJ] 백준 1238번 파티 (Java) (0) | 2021.05.19 |
|---|---|
| [BOJ] 백준 10451번 순열 사이클 (Java) (0) | 2021.05.18 |
| [BOJ] 백준 3344번 N-Queen (백트래킹x) (JAVA) (0) | 2021.05.17 |
| [BOJ] 백준 9657번 돌 게임3 (JAVA) (0) | 2021.05.16 |
| [BOJ] 백준 2573번 빙산 (Java) (0) | 2021.05.16 |
