1328. 고층 빌딩

특별히 이번 글은 내가 배운 내용을 적으려 한다.

1328번: 고층 빌딩

---

보자마자 DP로 풀면 되겠다는 생각이 들었다. 그런데 dp 정의를 생각하기가 너무나 어려웠다. 분명 $dp[i][j][k]$ 꼴이어야 하는데, $l$과 $r$은 당연하지만 $i$를 무엇으로 정의해야 할지 고민이었다. 빌딩의 총 개수로 놓으면 말이 안 되고.

 

그래서 1328번은 검색으로 풀었다. 검색한 결과 $i$는 가장 높은 빌딩의 높이로 정의해야 한다. $dp[i][j][k]$는 최고 높이가 $i-1$인 상황에서 각 빌딩의 높이를 1씩 높이고, 높이가 1인 빌딩을 어딘가에 끼워넣는 방법의 수로 이해해야 한다. 빌딩을 맨 왼쪽에 넣는 상황은 $dp[i-1][l-1][r]$, 맨 오른쪽에 넣는 상황은 $dp[i-1][l][r-1]$, 빌딩 사이 어딘가에 끼워넣는 방법은 $dp[i-1][l][r] \times (i-2)$이다. 높이 1짜리를 사이에 끼워넣어도 $l$과 $r$은 변하지 않지만, 끼워넣는 방법이 $i-2$가지이기 때문에 위와 같은 식이 나온다.

 

DP를 정의할 때 수열의 길이가 아니라 최댓값을 넣는 방식이 낯설었다. 기억해두자.

---

요즘 골드1 왜캐 어렵냐..