1328 고층빌딩

고층빌딩 (1328)

http://boj.kr/1328

이 문제도 교수님이 과제로 내줬다고 함.

(내가 처음 ps시작했을때 접했던 문제중에 몇 개 추천해달라고 해서 이거랑 텀프로젝트(내가 번역한 문제)를 추천했었는데 교수님은 이것만 과제로 냈음)

수요일에 애들한테 풀어주긴 했는데, 그냥 2번 과제도 올린김에 겸사겸사 이것도 올려본다.

DP문제를 별로 풀어보지 않았다면, 점화식을 생각해내기 힘들거다.

하지만 모든 DP문제가 그렇듯, 점화식 생각하는게 어렵지 코딩하는건 누워서 떡먹기~

$dp[N][L][R]:$ N개의 빌딩이 있을때 왼쪽에서 L개의 빌딩이 보이고 오른쪽에서 R개의 빌딩이 보이는 경우의 수

점화식은 $dp[N][L][R] = (L-2) \times dp[N-1][L][R] + dp[N-1][L-1][R] + dp[N-1][L][R-1]$ 이다.

왜냐하면 빌딩을 N-1개 세워보자. 그 다음 전부 높이를 1씩 올려준다. 그다음 높이가 1인 빌딩을 하나 끼워넣어보자. 맨 왼쪽이나 오른쪽에 끼워넣는 경우를 제외하고는 전부 왼쪽과 오른쪽에서 보이는 빌딩 개수에 변함이 없다. →  $(L-2) \times dp[N-1][L][R]$

그리고 맨 왼쪽에 빌딩을 끼워넣는 경우라면 왼쪽에서 보이는 빌딩의 개수가 하나 증가할 것이고, →  $dp[N-1][L-1][R]$

맨 오른쪽에 빌딩을 끼워넣는 경우라면 오른쪽에서 보이는 빌딩의 개수가 하나 증가할 것이다. →  $dp[N-1][L][R-1]$

그래서 위와 같은 점화식이 세워진다.

점화식 세웠으니 이제 base case만 잘 적어주면 코딩도 끝.

#include <cstdio> using namespace std; typedef long long ll; ll mod = 1e9+7LL; ll d[101][101][101]; ll f(int x, int l, int r) { if(l==1 && r==1) return (x==1); else if(l<1 || r<1 || l+r>x+1) return 0; ll &ret = d[x][l][r]; if(ret) return ret; return ret = ((x-2)*f(x-1,l,r)+f(x-1,l-1,r)+f(x-1,l,r-1))%mod; } int main() { int n,l,r; scanf("%d%d%d",&n,&l,&r); printf("%lld",f(n,l,r)); return 0; }