[PS] 2012 Daejeon 6117 Pole Arrangement

입력이 3개가 들어온다.

N L R이 들어온다

N은 길이가 전부 다른 막대기의 수이고, L은 왼쪽에서 봤을때 막대기의 개수

R은 오른쪽에서 보았을때 막대기의 개수이다.

본 문제는 가장 짧은 막대를 기준으로 잡아야 한다.

가장 긴막대를 기준으로 잡게되면, 긴 막대의 위치에 따라, L,R 값이 바뀌기 때문에

기준으로 잡으면 안된다.

하지만 가장 짧은 막대는 맨 왼쪽이나 맨 오른쪽만 아니면 어디에 끼워넣던지

L과 R에 영향을 미치지 않는다.

예를들어 N이 4이고 L=2, R=2 일때의 답을 구하고싶다고 가정하자.

막대기가 3개일때의 경우의 수는 다음과 같다.

가장 짧은 막대를 맨 왼쪽에 붙였을때 (2,2)가 되는 경우는

N이3일때 (1,2)인 경우밖에 없다.

가장 짧은 막대를 맨 오른쪽에 붙였을때 (2,2)가 되는 경우는 (2,1) 인경우가 있다.

그리고 (2,2)인 경우에서 가장짧은 막대를 가운데 어디든 끼워넣어도 (2,2)가 된다.

N이 3일때 끼워넣을수 있는곳은 2곳 .

즉, N-1개이다.

그러면 N이 4일때 (2,2)는

N이3일때의 (1,2)의 개수 + (2,1)의 개수 + (2,2)의개수 * (N-1-1)이 된다.

N이 2일때의 경우는 (1,2) , (2,1) 각각 1가지 밖에 없다는걸 알고있다.

그러면 N개의 막대가 있을떄 (1,N) , (N,1)인 경우도 단 한가지 밖에 없다.

N의 범위가 1<= N <=20 이다.

그리고 L과 R도 1~20 이므로 이 3가지 변수에 대해 메모테이블을 만들고

상향식 동적 계획법으로 값을 채우면된다.