알러지가 심한 친구들

  • int_solution
    int_solution

    보기에 나온 예제대로 하면

    2
    4 6
    cl bom dara minzy
    2 dara minzy
    2 cl minzy
    2 cl dara
    1 cl
    2 bom dara
    2 bom minzy
    10 7
    a b c d e f g h i j
    6 a c d h i j
    3 a d i
    7 a c f g h i j
    3 b d g
    5 b c f h i
    4 b e g j
    5 b c g h i

    를 입력했을 경우
    첫 번째 경우는 계산되는 수가 23
    두 번째 경우는 계산되는 수가 45 로
    2^6과 2^7에 비해 계산해야되는 수를 1/3 정도로 줄였는데도 시간초과가 나네요.. ㅜㅜ 풀려면 얼마나 더 줄여야 되는건가요??


    10년 전
1개의 댓글이 있습니다.
  • Being
    Being

    우선 예제만 가지고 큰 데이터에 대해 경우의 수가 줄어드는 비율을 이야기하는 것은 어렵습니다. 어떻게 구현하셨는지는 모르겠지만, 실제로 큰 데이터의 경우 1/3보다 더 줄어들기는 할 것입니다. 그러나, 경우의 수를 1/100으로 줄인다 하더라도 250의 1/100은 어마어마하게 큰 수인 것 역시 생각하셔야 합니다.


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