질문이 하나 더!!!

  • LucidaSH
    LucidaSH

    음 ...
    1 부터 N 까지의 N 개의 자연수가 있습니다.
    이를 일렬로 늘어놔서 만들 수 있는 수열은
    n! 가지의 경우가 있죠
    그런데
    수열의 i 번째 수를 p[i] 라고 했을 때
    | pi] - i | <= k ( k는 상수로 6이하 )
    인 경우의 수열만 counting 하였을 때
    경우의 수 가 몇가지나 될지 찾는 문제입니다....
    n 은 100 이하 이구 K 는 6이하 입니다.
    ㅠㅠ DP 같은데 잘 모르겠네요 휴

    [이 글은 과거 홈페이지에서 이전된 글입니다. 원문보기]


    12년 전
2개의 댓글이 있습니다.
  • JongMan
    JongMan

    O(n * 2^(k*2)) 로는 확실히 풀릴 듯 =3=3=3


    12년 전 link
  • LucidaSH
    LucidaSH

    네ㅋㅋ
    결국 고민 끝에 그렇게 푸러써요 ㅎㅎ
    p.s ) 2k + 1 ...;;;;


    12년 전 link
  • 정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.