1058번 - 친구
안녕하세요.
이 문제 플로이드로 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으로 담길거라 생각했고, 시간복잡도를 줄여보고 싶었습니다.
어디가 잘 못 되었는지 알려주실 수 있나요 ??
그 두 부분 수정해서 제출해보니 맞네요
1년이나 지났지만... 저도 어디가 틀렸는지 궁금해서 찾아보다가 알게되어 댓글 남깁니다 ㅋㅋㅋ
답변 감사합니다! 비트연산 쓸 때 조심해야겟네요 ㅎㅎ
댓글을 작성하려면 로그인해야 합니다.
adh0463 6년 전 1
안녕하세요.
이 문제 플로이드로 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으로 담길거라 생각했고, 시간복잡도를 줄여보고 싶었습니다.
어디가 잘 못 되었는지 알려주실 수 있나요 ??