티스토리 뷰
https://www.acmicpc.net/problem/1328
1328번: 고층 빌딩
상근이가 살고있는 동네에는 빌딩 N개가 한 줄로 세워져 있다. 모든 빌딩의 높이는 1보다 크거나 같고, N보다 작거나 같으며, 같은 높이를 가지는 빌딩은 없다. 상근이는 학교 가는 길에 가장 왼
www.acmicpc.net
처음에 뭔가 수학에서의 조합을 이용해 풀 수 있을 것 같았는데 제 아이디어로는 빌딩 사이로 1개만 넣는 거라 고민 끝에 다른 분들의 아이디어를 참고했습니다.
아이디어 : dp[n+1][l][r] 을 구하자 (n+1 : 전체 빌딩, l : 왼쪽에서 본 빌딩 수, r : 오른쪽에서 본 빌딩 수)
결론부터 말하자면
dp[n+1][l][r] = dp[n][l-1][r] + dp[n][l][r-1] + dp[n][l][r] * (n-1) 입니다.
1) dp[n][l-1][r] 만큼 놓을 수 있는 경우에서 맨 왼쪽에 가장 작은 빌딩을 놔두면 dp[n+1][l][r] 이다
2) dp[n][l][r-1] 만큼 놓을 수 있는 경우에서 맨 오른쪽에 가장 작은 빌딩 놔두면 dp[n+1][l][r] 이다
3) dp[n][l][r] 만큼 놓을 수 있는 경우에서 n개의 빌딩 사이인 n-1 군데에 가장 작은 빌딩 놔두면 dp[n+1][l][r] 이다
이렇게 3가지로 구분할 수 있습니다.
코드는 다음과 같습니다.
'알고리즘 > 백준' 카테고리의 다른 글
| 백준 2151 거울 설치 C++ (0) | 2022.02.22 |
|---|---|
| 백준 1135 뉴스전하기 C++ (0) | 2022.02.22 |
| 백준 1765 닭싸움 팀 정하기 C++ (0) | 2022.02.07 |
| 백준 16562 친구비 c++ (0) | 2022.02.07 |
| 백준 11402 이항계수 4 C++ (0) | 2022.01.15 |
댓글