CLOCKSYNC 완전 탐색으로 잘 푼거 같은데 시간 초과...

  • qodot
    qodot 
    def dfs(cb, cr):
    global r

    if r < cr:
        return

    if all(map(lambda x: x % 12 == 0, c)):
        r = cr
        return

    if cb == 10:
        return

    for i in range(0, 4):
        for j in t[cb]: c[j] += 3 * i
        dfs(cb + 1, cr + i)
        for j in t[cb]: c[j] -= 3 * i

for t in range(input()):
    t = [[0, 1, 2], [3, 7, 9, 11], [4, 10, 14, 15], [0, 4, 5, 6, 7], [6, 7, 8, 10, 12], [0, 2, 14, 15], [3, 14, 15], [4, 5, 7, 14, 15], [1, 2, 3, 4, 5], [3, 4, 5, 9, 13]]
    c = map(int, raw_input().split())
    r = 30

    dfs(0, 0)

    print r

    완전 탐색으로 풀었고, 별거 아닌 최적화지만 넣어 보았는데 (if r < cr: return 부분...) 자꾸 시간초과가 뜨네요 ㅜㅜ

    혹시 불필요한 탐색을 하고 있는걸까요?

    첨에 루비로 해서 안되길래 파이썬으로 바꿔 봤는데 역시나네요 ㅜㅜㅜ 파이썬 문제라기에는 파이썬으로 맞춘 사람도 있어서 ㅜㅜ


    9년 전
6개의 댓글이 있습니다.
  • Kureyo
    Kureyo

    파이썬으로 맞은 1인입니다만..완전탐색으론 답이나올수없습니다
    문제 값에 트릭이 있으니 잘 살펴보세요


    9년 전 link
  • qodot
    qodot

    그런가요 ㅜㅜ "알고리즘 문제 해결 전략 책을 뒤져 보았는데 완전탐색으로 풀더라구요...ㅜㅜ


    9년 전 link
  • Kureyo
    Kureyo

    힌트

    스위치에 연결된 시계를 나열하는게 아니라
    각 시계별로 연결된 스위치를 나열해보세요
    하나의 특징이 보일것입니다


    9년 전 link
  • qodot
    qodot

    일단 완전탐색을 자바로 구현했더니 풀렸습니다... ㅜㅜ
    그리고 나서 Kureyo님의 코드를 보았는데도 이해가 안되네요...

    sw 테이블이 어떤 의미를 담고 있는건지 힌트 + 코드를 보아도 잘 이해가 안되니 저도 제가 답답하네요 ㅜㅜ


    9년 전 link
  • Kureyo
    Kureyo

    강력 스포일러!

    시계와 스위치 관계를 잘 보시면..
    13번 시계를 조절할수 있는건 9번 스위치밖에 없습니다.
    만약 13번 시계가 3시로 되어있다면 9번 스위치는 무조건 3번 눌러야겠죠?
    그다음엔 9번 시계를 보시죠
    9번 시계를 조절할수있는 스위치는 1번 스위치와 9번 스위치였습니다.
    근데 9번 스위치를 3번눌러야하는건 정해진 사실이기 때문에,
    9번 시계의 값을 보고 1번 스위치를 누를 횟수 역시 정해집니다.
    이런식으로 하나씩 지워나가다보면 모든 스위치의 누름 횟수가 항상 필연적으로 정해짐을 알수있습니다.


    9년 전 link
  • qodot
    qodot

    덕분에 추가로 해결하였습니다! 이런 방법이 있다니... 어떻게 생각해내시는거죠... ㅋㅋ
    30ms에 끝나네요 ㅋㅋㅋ
    자바로 완전탐색은 4000ms에 육박하는데...

    감사합니다!


    9년 전 link

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