adh0463   6년 전

안녕하세요.

이 문제 플로이드로 AC 받긴 했습니다만, 시간 복잡도를 O(N^2)으로 줄이고 싶어서 비트마스크를 이용해서 소스를 작성했습니다만.. 어디가 잘못됐는지 10%에서 자꾸 WA 나오네요.

집합개념으로 rel[i]에는 i번째 사람의 친구들이 비트로 저장되어 있습니다. 모두 저장이 되면, 모두 순회하며 i번째 친구의 친구를 tmp에 OR로 담아줍니다. rel[i]의 오염을 방지하고자 res 변수에 rel[i] | tmp로 담아줍니다.

이렇게하면 i번째 자신이 친구로 인식될 수도 있으므로 계산할 때 i!=j로 걸러줍니다. 이렇게 계산된 값의 최대값을 추출하는 식으로 작성했습니다만.. 뭐가 잘못된걸까요 ??

N제한이 50이기에 long long으로 담길거라 생각했고,  시간복잡도를 줄여보고 싶었습니다.

어디가 잘 못 되었는지 알려주실 수 있나요 ??

bvba   5년 전

  1. tmp 는 long long int 형 이여야 합니다.
  2. 1 << j 는 int형으로 처리되기 때문에 1llu << j 처럼 long long int 형이여야 합니다.

그 두 부분 수정해서 제출해보니 맞네요

1년이나 지났지만... 저도 어디가 틀렸는지 궁금해서 찾아보다가 알게되어 댓글 남깁니다 ㅋㅋㅋ

adh0463   5년 전

답변 감사합니다! 비트연산 쓸 때 조심해야겟네요 ㅎㅎ

댓글을 작성하려면 로그인해야 합니다.