[백준][DP] 1328번 고층빌딩

문제

N, L, R이 주어진다. N개의 건물을 왼쪽에서 보았을 때는 L개가 보이고 오른쪽에서 보았을 때 R개가 보이는 경우의 수를 구하시오.

문제 출처: 백준 온라인저지(https://www.acmicpc.net/problem/1328)

풀이

처음에 보자마자 너무 어렵다고 생각이 들었습니다! 그리고 아주 이상한 방법으로 많이 접근을 했습니다. 다이나믹 프로그래밍 카테고리에서 골랐기 때문에 dp로 풀어야겠다는 생각은 들었지만 점화식을 세울 수 없었습니다. 처음엔 1~N까지의 건물이 주어질 때 높이가 N인 건물을 고정시키면 왼쪽, 오른쪽으로 경우의 수를 쪼갤 수 있어서 그 방법을 통해서 시도해보려 했지만 너무 어렵고 무식한 방법이었습니다. 결국 다른 분들이 풀이한 것들을 보고 힌트를 얻어서 풀었습니다. N-1개의 건물이 있을 때 N개의 건물이 되기 위한 점화식을 생각해내기위해 높이가 1인 건물을 추가한다고 생각하면 쉽게 풀립니다.(사실 높이가 N인 건물을 추가하는 것인데 명확하게 이 부분을 이해하진.. 못했습니다.) 

dp[N][L][R] = N개의 건물이 있을 때 왼쪽에서는 L개의 건물이 보이고 오른쪽에서는 R개의 건물이 보이는 경우의 수

만약 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://github.com/kswim/Algorithm/blob/master/DP/1328.cpp