[백준] No.8895 - 막대 배치 (C++, DP)

문제

 

https://www.acmicpc.net/problem/8895

8895번: 막대 배치

 

풀이

 

solved.ac 난이도: Gold 1

 

[백준] 고층 빌딩(1328) 문제와 완전히 동일한 풀이로 해결할 수 있다.

 

dp[stick][l][r]를 stick 개수의 막대를 놓았을 때 왼쪽에서 l개, 오른쪽에서 r개가 보이는 경우의 수 라고하자.

 

모든 막대를 항상 가장 큰 막대부터 작은 막대의 순서대로 놓는다고 생각해보자.

지금까지 stick - 1개의 막대를 놓았다면 다음으로 막대를 놓는 경우는 3가지가 존재한다.

 

 

1. 가장 왼쪽에 놓는다.

 

다음으로 놓는 막대는 지금까지 놓은 어느 막대들 보다도 작으므로 왼쪽에서 본 막대의 개수가 +1 증가한다.

따라서 dp[stick-1][l-1][r]가 다음 막대를 가장 왼쪽에 놓는 경우에 가능한 모든 배치의 수이다.

(다음 막대를 왼쪽에 놓으므로 왼쪽에서 보이는 막대의 개수가 l -1에서 l개로 + 1 증가함.)

 

 

2. 가장 오른쪽에 놓는다.

 

다음으로 놓는 막대는 지금까지 놓은 어느 막대들 보다도 작으므로 오른쪽에서 본 막대의 개수가 +1 증가한다.

따라서 dp[stick-1][l][r-1]가 다음 막대를 가장 오른쪽에 놓는 경우에 가능한 모든 배치의 수이다.

 

 

3. 이외의 공간에 놓는다.

 

이외의 공간에 배치한다면, 해당 막대는 다른 모든 막대들 보다 작으므로 왼쪽이나 오른쪽에서 볼 수 있는 막대의 개수에는 변함이 없다.

이때 배치할 수 있는 공간의 수는 막대의 양 사이드를 제외한 안쪽으로 stick(막대의 개수) - 2(양 사이드) 개다.

그러므로 stick-1개의 막대를 배치한 경우에 왼쪽에서 l개 오른쪽에서 r개가 보이는 경우의 수 dp[stick-1][l][r]에 stick -2를 곱해준다.

이 값이 다음 막대를 양 사이드 이외의 공간에 배치하는 경우의 수이다.

dp[stick-1][l][r] * (stick -2)

 

 

최종적으로 dp[stick][l][r] 의 값은 3가지 경우의 수를 합친 값으로 계산할 수 있다.

dp[stick][l][r] = dp[stick-1][l-1][r] + dp[stick-1][l][r-1] + dp[stick-1][l][r] * (stick -2)

 

 

참조 풀이

 

[ BOJ 백준 1328번 - 고층 빌딩 ] 해설 및 코드 - 징검다리

 

 

 

코드