티스토리 뷰

문제 풀이

[BOJ 8895] 막대 배치

RiKang 2018. 1. 10. 11:17
반응형

 2012 ACM-ICPC Daejeon regional 의 기출문제입니다. 백준 8895에서 채점할 수 있습니다.


요약 )


 문제는 높이가 1,2,...,n 인 n개의 막대를 일렬로 세울 때, 왼쪽에서 보이는 막대가 l개, 오른쪽에서 보이는 막대가 r개가 되는 경우의 수를 구하는 것입니다. 이 문제는 '문제'를 '하위 문제'들로 나누어 해결하는 동적계획법으로 해결할 수 있습니다.


DP 배열 구하기 )


 먼저 DP문제를 정의해야 합니다. 다행히 이 문제는 있는 그대로, 아래처럼 DP를 정의해도 해결할 수 있습니다.


  dp[n][l][r] = n개의 막대, 왼쪽에서 보이는 막대가 l개, 오른쪽에서 보이는 막대가 r개일 때의 답


 이제 하위 문제를 찾아야 합니다. 높이가 n인 막대의 위치를 기준으로 하위 문제를 설정하여도 문제를 해결할 수 있지만, 다소 복잡합니다. 따라서 이 풀이에서는 높이가 1인 막대의 위치를 기준으로 하위 문제를 설정하도록 하겠습니다.


하위 문제 1 ) 높이가 1인 막대의 위치가 제일 왼쪽인 경우

-> 높이가 1인 막대를 치웠다고 생각해 봅시다.

-> 왼쪽에서 보이는 개수만 한 개 줄어듭니다.

-> n-1개의 막대, 왼쪽에서 l-1개 보이고, 오른쪽에서 r개 보이는 상황과 동일합니다.

-> dp[n-1][l-1][r] 에 그 답이 저장되어 있습니다.


하위 문제 2 ) 높이가 1인 막대의 위치가 제일 오른쪽인 경우

-> 높이가 1인 막대를 치웠다고 생각해 봅시다.

-> 오른쪽에서 보이는 개수만 한 개 줄어듭니다.

-> n-1개의 막대, 왼쪽에서 l개 보이고, 오른쪽에서 r-1개 보이는 상황과 동일합니다.

-> dp[n-1][l][r-1] 에 그 답이 저장되어 있습니다.


하위 문제 3 ) 높이가 1인 막대의 위치가 2 ~ n-1 위치인 경우

-> 높이가 1인 막대를 치웠다고 생각해 봅시다.

-> 보이는 막대 개수는 변하지 않습니다.

-> n-1개의 막대, 왼쪽에서 l개 보이고, 오른쪽에서 r개 보이는 상황과 동일합니다.

-> dp[n-1][l][r] 에 그 답이 저장되어 있습니다.


 하위 문제 1, 2 는 1개의 위치, 3은 n-2개의 위치에서 가능하므로 아래와 같은 관계식이 성립합니다.


  dp[n][l][r] = (하위 문제 1) + (하위 문제 2) + (n-2) * (하위 문제 3)

  dp[n][l][r] = dp[n-1][l-1][r] + dp[n-1][l][r-1]  + (n-2) * dp[n-1][l][r]


1
2
3
4
5
6
7
8
9
10
11
12
13
14
// code by RiKang, weeklyps.com
 
long long dp[25][25][25]; // 정답 = dp[n][l][r]
 
void get_dp(){
    dp[1][1][1= 1;
    for(int i=2; i<=20; i++){
        for(int j=1; j<=i; j++){
            for(int k=1; k<=i; k++){
                dp[i][j][k] = dp[i-1][j-1][k]+dp[i-1][j][k-1]+(i-2)*dp[i-1][j][k];
            }
        }
    }
}
cs


정답 구하기 )


 DP 배열이 구해진 상태에서는 dp[n][l][r]을 출력해주면 끝입니다.


1
2
3
4
5
6
// code by RiKang, weeklyps.com
 
void solve(){
    scanf("%d %d %d",&n,&l,&r);
    printf("%lld\n",dp[n][l][r]);
}
cs


최종 코드 )


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
// code by RiKang, weeklyps.com
// 2012 ACM-ICPC Daejeon regional - H
// BOJ 8895 막대 배치
// O(n^3) solution
 
#include <bits/stdc++.h>
using namespace::std;
 
int n, l, r;
long long dp[25][25][25]; // 정답 = dp[n][l][r]
 
void get_dp(){
    dp[1][1][1= 1;
    for(int i=2; i<=20; i++){
        for(int j=1; j<=i; j++){
            for(int k=1; k<=i; k++){
                dp[i][j][k] = dp[i-1][j-1][k]+dp[i-1][j][k-1]+(i-2)*dp[i-1][j][k];
            }
        }
    }
}
 
void solve(){
    scanf("%d %d %d",&n,&l,&r);
    printf("%lld\n",dp[n][l][r]);
}
 
int main(){
    get_dp();
    int t;
    scanf("%d",&t);
    while(t--){
        solve();
    }
    return 0;
}
cs


반응형

'문제 풀이' 카테고리의 다른 글

[BOJ 8894] Pattern Lock  (0) 2018.01.11
[BOJ 8891] 점 숫자  (0) 2018.01.10
[BOJ 8896] 가위 바위 보  (0) 2018.01.09
[BOJ 8892] 팰린드롬  (0) 2018.01.09
함수 문제 풀이  (0) 2018.01.04