질문이 하나 더!!! LucidaSH 음 ... 1 부터 N 까지의 N 개의 자연수가 있습니다. 이를 일렬로 늘어놔서 만들 수 있는 수열은 n! 가지의 경우가 있죠 그런데 수열의 i 번째 수를 p[i] 라고 했을 때 | pi] - i | <= k ( k는 상수로 6이하 ) 인 경우의 수열만 counting 하였을 때 경우의 수 가 몇가지나 될지 찾는 문제입니다.... n 은 100 이하 이구 K 는 6이하 입니다. ㅠㅠ DP 같은데 잘 모르겠네요 휴[이 글은 과거 홈페이지에서 이전된 글입니다. 원문보기] 15년 전
2개의 댓글이 있습니다. JongMan O(n * 2^(k*2)) 로는 확실히 풀릴 듯 =3=3=3 15년 전 link LucidaSH 네ㅋㅋ 결국 고민 끝에 그렇게 푸러써요 ㅎㅎ p.s ) 2k + 1 ...;;;; 15년 전 link 정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.
LucidaSH
음 ...
1 부터 N 까지의 N 개의 자연수가 있습니다.
이를 일렬로 늘어놔서 만들 수 있는 수열은
n! 가지의 경우가 있죠
그런데
수열의 i 번째 수를 p[i] 라고 했을 때
| pi] - i | <= k ( k는 상수로 6이하 )
인 경우의 수열만 counting 하였을 때
경우의 수 가 몇가지나 될지 찾는 문제입니다....
n 은 100 이하 이구 K 는 6이하 입니다.
ㅠㅠ DP 같은데 잘 모르겠네요 휴
15년 전