2010 ACM-ICPC 서울대회 인터넷예선 D. 정육면체 문제 질문입니다.

  • 김우현
    김우현

    개인적으로 이 문제가 재미있어서 생각을 해보았는데요.
    좋은 솔루션에 대해 알고 싶어 토의 글로 올립니다.

    지금까지는 문제를 3차원 DP로 접근했습니다.
    D[W][L][H] = 정육면체 크기가 W,L,H일 때 최소 절단 횟수

    이를 구하기 위해서 각각의 변에 대해서 하나씩 잘라보는 접근으로
    시간복잡도가 O( W*L*H*(W+L+H) ) 되는 접근 방식을 생각했습니다.
    하지만 여기서 저의 한계라 ㅠ; 알고스팟님들의 아이디어를 듣고 싶습니다!

    소소한 최적화를 생각한 것으로

    1. W<=L<=H 순서를 항상유지
    2. D[W][L][H]를 구하는 과정에서 최대로 각변의 절반 길이까지만 잘라보기.
    3. 한변이 1인경우 예외처리 d[1][L][H] = L*H-1
    4. Precalculation

    이 있습니다.


    13년 전
7개의 댓글이 있습니다.
  • lewha0
    lewha0

    저도 궁금해서 다른 학생들에게 이야기를 들어봤는데, 대부분 저런 식으로 처리한 듯 했습니다. 순서를 유지하고, 절반만 잘라보면 그럭저럭 빠른 듯 하더라고요.
    개인적으로는 |W-L|, |L-H|, |W-H| 에 대해서만 잘라보면 될 것 같은데, 확인해보진 않았습니다. 세 변의 길이가 서로 다를 때, 자른 결과도 세 변의 길이가 다를 필요는 없을 것 같아서요.. 그리고 추가로, W, L, H 의 길이로도 잘라 볼 필요가 있을 것 같고요.


    13년 전 link
  • 전명우
    전명우
    • 메모리제이션까지 사용하면 시간을 확실히 줄일 수 있습니다.

    13년 전 link
  • Kureyo
    Kureyo

    저도 항상 자를때 정사각형 새로이 하나씩은 만들어져야한다고 생각하는데..
    이렇게 짜보신분 없으신가요 'ㅡ'; WA를 받으려나


    13년 전 link
  • Arena
    Arena

    저도 대회때 최소길이를 기준으로 매번 정사각형 만드는 방식을 생각했는데
    시간상 넣어보지는 못했네요 ㅜㅜ
    제가 알아본 ac받은 팀은 전부 DP로 푸셧네요


    13년 전 link
  • 김우현
    김우현

    유키님의 아이디어를 구현해 봤는데
    예제의 3번째 케이스인 5 6 6이 반례가 됩니다. ㅠ

    최소길이를 기준으로 사각형을 만드는 것도 마찬가지로 반례가 되겠네요.


    13년 전 link
  • wookayin
    wookayin

    저도 대회때 O(n^4) 알고리즘밖에 안 떠올라서 고민하다가 혹시나 하고 O(n^4)를 짜봤는데, 로컬에서 1.0초 미만으로 나오길래 놀라면서 DP로 맞았던 기억이 있습니다.
    W, L, H에 대해 가능한 6가지 순열에 대해 f(W, L, H) 값은 같기 때문에, W<=L<=H가 되도록 n^3/6의 loop를 돌리고, 짤라보는 루프 k는 H까지만 돌려서 각각 k,W-k / k, L-k / H, L-k 를 시도해보면 됩니다. 계산이 다 되면 6군데에 값을 넣어주고요.
    좀 더 최적화해서 k가 H/2 까지만 돌려도 되는데 저희는 k를 그냥 H까지만 돌리고도 로컬에서 돌려보니 빠르게 나온 듯 합니다.


    13년 전 link
  • GondoR
    GondoR

    저희팀도 O(n^4) 알고리즘으로 적당히 최적화(wookayin 님 만큼(?)) 하니 1초안에 충분히 나오더라구요~


    13년 전 link

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