어제 ACM ICPC H번문제..질문이요.

  • 거부기
    거부기

    HOMEWORK 문제였는데...
    정확하게 어떻게 풀지 몰라서;;;
    동적으로 했긴 했는데
    이게 맞는건지 아닌건지 모르겠습니다.
    그래서 정답을 못 맞췃고;;;
    정확하게 어떻게 풀어야 하는지 알고 싶어요.
    소스는..올리라고 하시면 그 때 올리겠습니다.

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


    16년 전
5개의 댓글이 있습니다.
  • Corea
    Corea

    KOI8팀으로 참가한 Corea입니다..;;;
    저는 H번 O(N!)의 시간복잡도로 백트랙킹으로 해결했습니다..
    전화하는 순서에 있어서 백트랙킹으로..;;
    자세한 답 원하시면 댓글(...)달아주세요


    16년 전 link
  • 거부기
    거부기

    소스는 밑에 파일로 첨부하였습니다.
    그럼 어떤상황에서 잘못된건지 알 수가 없네요;;
    분명 잘못된건 알겠는데;;; ㅡㅠㅡ
    그리고 백트래킹이라면...모든 경우의 수를 비교하신건지 알고 싶어요.


    16년 전 link
  • Corea
    Corea

    저는 동적계획법으로 생각조차 안해봐서(....)
    어떻게 정의를 하셨는지, 점화식은 어떻는지를 설명해주셨으면 합니다.
    그리고 백트래킹 코드를 첨부할게요:)
    모든 경우의 수를 비교했다는 의미가 무엇인진 정확하게 모르겠지만..
    가능한 모든 경우를 체크했습니다:)


    16년 전 link
  • 거부기
    거부기

    일단 급하게 한거라;;;
    T(n) = min + max + t
    여기서 최소값하고 최대값을 뺀 나머지에서 걸리는 시간을 d라고 하면
    t값은 d가 max보다 작으면 0이고 크면 t = d - max가 되는거죠.
    d는 이제 n개 중에서 최소값하고 최대값을 뺀 나머지에서 걸리는 시간 T(n-2) 라고 보시면 될거 같아요.\
    근데 제가 문제를 잘못이해한것도 있고 해서;;;
    틀린거 같아요;;;
    근데 어디서 틀렸는지 잘모르겠더라구요;;;
    ...ㅜ.ㅡ (퍽퍽)


    16년 전 link
  • kcm1700
    kcm1700

    모든 상태를 고려하는 (2^N 개의 상태) 다이나믹으로도 풀리긴 합니다만,백트래킹이 좋습니다. 수가 작기 때문에 그렇게 푸는게 맞구요,
    그런데 거부기님이 제시하신 점화식은 어떻게 적용되는지 잘 모르겠네요~


    16년 전 link

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