백트래킹(!?)문제 질문입니다~

  • LucidaSH
    LucidaSH

    안녕하세요-_-
    이번 서울 리저널 발린 ;;;
    08 뉴비 김상훈 입니다.
    대회 전에 연습 때 부터 해결 하지 못한 질문인데 ;;;
    http://acm.pku.edu.cn/JudgeOnline/problem?id=3134
    http://acm.pku.edu.cn/JudgeOnline/problem?id=1945
    아마 두 문제는 거의 비슷한 문제 인 것같은데요 ;;;
    3134 번 문제의 경우 n 이 1,000 이라 백트래킹으로도 쉽게 ;; 답을 낼 수 있었는데
    1945 번 문제는 n 이 20,000 이라 .,, 제 코딩 실력으로는(?!) 백트래킹으로는 도저히 답이 나올 생각을 안하는데요 ;;
    ....
    1945 번 의 솔루션도 백트래킹이 맞는 건가요 ?!
    실제로 status 를 보면 -_- 속도 / 메모리로 상위권인 사람들은 보니 대충 ...
    DB 냄새가 나는데 ;;;
    ㅠㅠ 고수님들의 답변 부탁드립니다.

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


    15년 전
5개의 댓글이 있습니다.
  • JongMan
    JongMan

    O(n^2) BFS 로 풀면 안 되나? ^^;;스탯 보니까 막 20000바이트짜리 솔루션도 있고 ㄷㄷㄷㄷ
    근데 좀 그리디 삘인데 ㅋㅋㅋ


    15년 전 link
  • tompi
    tompi

    1945 어려워요 ㅠㅠ


    15년 전 link
  • Corea
    Corea

    저는 1945.. BFS로 해결했네요...


    15년 전 link
  • LucidaSH
    LucidaSH

    쪼금만 더 자세히 ㅠ_ㅠ 설명 해주세용 ㅋㅋ


    15년 전 link
  • josh
    josh

    아마도... 두 숫자로 표시할 수 있는 상태들에 대한 BFS를 하라는 이야기 인 것 같습니다.
    (x, 31)로 갈 수 있는 상태들인:
    (1, 32)
    (1, 30)
    (2, 29)
    (2, 33)
    등등...
    공간복잡도는 O(N^2)가 되고, 시간복잡도도 마찬가지. 상태를 normalize(작은/큰 숫자가 앞으로 오게) 하면 절반으로 줄어듭니다


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