ALLERGY 문제 시간 초과 (subset으로 풀었습니다.)

  • ybs
    ybs

    알러지 문제를 subset을 이용하여 풀어보았는데, 예상대로 시간 초과가 나오네요. 최악의 경우 2^50 계산이라 그런 것 같습니다.
    중간중간 빠져나올 수 있을 때의 예외를 넣긴 했으나 무리네요.

    혹시 다른 알고리즘을 써야한다면 어떤 알고리즘을 쓰면 될지 도움 부탁드립니다.


    8년 전
2개의 댓글이 있습니다.
  • coldradio
    coldradio

    그 방법으로 해도 풀리긴 합니다. 시간이 1초 미만으로 떨어지긴하네요. 50ms밑도 많은걸 보면 분명 효율적인 방법이 있을텐데요.

    구현할때 친구 수가 50이하이므로 64비트 정수형에 친구를 비트필드로 표현해주고 음식이 추가될때마다 먹을 수 있는 친구를 없애줍니다.

    더 효율적인 방법은 다른 분의 댓글로~


    8년 전 link
  • coldradio
    coldradio

    함수 원형은 f(음식 인덱스, 친구 비트필드, 지금까지 베스트 값) 정도 일지 싶네요.


    8년 전 link

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