[SwExpertAcademy] Pole

문제 출처 :

https://swexpertacademy.com/main/learn/course/subjectDetail.do?subjectId=AWWxyRM6AhMDFAW4

알고리즘 분석 :

문제 해결에 필요한 사항

1. Dynamic Programming

2. 점화식 세우는 방법

만약 1인 건물을 N - 1개의 건물에서 제일 앞으로 추가한다면 왼쪽에서 보는 건물의 수가 증가할 것이다.

이렇게 맨 앞에 추가할 수 있는 경우의 수는 dp[N - 1][L - 1][R] 일 것이다.

dp[N - 1][L - 1][R]에서 제일 왼쪽에 높이 1의 건물을 추가하면 N - 1 + 1이 되고 L - 1 + 1이 되기 때문이다.

이와 마찬가지로 가장 오른쪽에 건물을 추가할 수도 있는데 그 경우는 dp[N - 1][L][R - 1]가 된다.

그리고 중간에 건물을 추가한다면 높이가 1이기 때문에 어느 곳에든 추가해도 왼쪽, 오른쪽에서 보이는 건물의 수는 그대로다.

즉 dp[N - 1][L][R]의 수가 가장 양 옆을 제외한 N - 2개가 생긴다.

결국 점화식은 다음과 같다.

dp[N][L][R] = dp[N - 1][L - 1][R] + dp[N - 1][L][R - 1] + dp[N - 1][R][L] * (N - 2)

이 문제는 백준 빌딩 세우기 문제와 같다.

https://kswims.tistory.com/175

소스 코드 : 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24

#include <iostream>   typedef long long ll;   ll dp[22][22][22];   int main() {     int tCase;     scanf("%d", &tCase);     dp[1][1][1] = 1;     for (int i = 2; i <= 20; i++)         for (int j = 1; j <= 20; j++)             for (int k = 1; k <= 20; k++)                 dp[i][j][k] = dp[i - 1][j - 1][k] + dp[i - 1][j][k - 1] +( (i - 2)*dp[i - 1][j][k]);                  for (int tc = 1; tc <= tCase; tc++) {         int n, l, r;         scanf("%d %d %d", &n, &l, &r);                  printf("#%d %lld\n", tc, dp[n][l][r]);     }     return 0; }   Colored by Color Scripter

cs