[질문] 경우의 수 문제 하나만 질문하자

[익명(39.7)]

N이라는 숫자가 주어질때, 1 ~ N까지 줄을 세우는 방법은 N! 이면,
1 3 2 4 ... 같이 증가 감소를 번갈아하거나,
3 1 4 2 ... 같이 감소 증가를 번갈아하는 수열의 경우의 수는?
(1<= N <=300)
이거 어케푸냐 ㅇㅇ;;

[메리체리(mrscherry)]

dp[i][j]=길이가 i이고 j로 시작하는 순열 개수

[메리체리(mrscherry)]

+증가부터 시작하는 순열

[익명(221.153)]

주어진 모든 수를 다 사용해야함

[메리체리(mrscherry)]

이해못하셨군

[익명(221.153)]

헉; 잠만 생각해범;;

[메리체리(mrscherry)]

정확히말하면 dp[i][j]는 1~i로된 순열이고 증가로 시작할때 j(<=i)로 시작하는 순열개수임

[익명(221.153)]

음 점화식이 잘 안세워지는데 추가힌트없냐

[익명(221.153)]

dp[3][1]은 1 3 2 해서 1개고, dp[4][1]은 1 4 2 3, 1 3 2 4 해서 2개인데 둘이 연관성이 안보임

[메리체리(mrscherry)]

길이 i 순열에서 첫원소가 정해졌으면 그 뒤의 원소들이 만족해야할 조건은 두번째 원소가 첫원소보다 크다+감소부터 시작한다임

[메리체리(mrscherry)]

길이 4 순열에서 첫원소가 2라면 남은 원소는 1 3 4이고 두번째로 가능한건 3 4인데

[메리체리(mrscherry)]

1 3 4를 그냥 1 2 3으로 바꾸고 두번째로 가능한게 2 3인걸로 봐도 경우의수는 같음

[익명(221.153)]

아...시발ㅋㅋㅋ이렇게 생각할수가있구나

[메리체리(mrscherry)]

증가부터 시작하는걸 dp1이라고 하고 감소부터 시작하는걸 dp2라고 하면 dp1[i][j]=dp2[i-1][j]+...+dp2[i-1][i-1]이 되겠지

[익명(221.153)]

아 점화식은 다시 생각해볼라그랫는데;;

[메리체리(mrscherry)]

ㅋㅋㅈㅅ

[익명(221.153)]

근데 이런식으로 생각하는방법은 몰랏는데 하나배우네 ㄱㅅㄱㅅ

[신동원(223.38)]

n log n 됨? - dc App

[익명(221.153)]

N 범위가 300까지라서 N^3이면 충분