2^22+22개 내에서 사이클이 나와야 하는데, 그러면 상수시간만에 중복되는지 확인을 해야해서 일단 bitmask느낌으로 풀었습니다.
(막 질문 글 찾아보니 사이클은 최대 500개 내로 형성된다는데, 실전에서 이 문제를 풀면 그걸 직접 구할 수는 없으니까 일단 2^22+22개라고 생각을 하고 하겠습니다,,)
무튼, 저는
선공이 이기는 경우와 후공이 이기는 경우를 매 단계마다 저장해둡니다.
그러고 매 단계마다 bit연산을 통해(예를 들어, 돌이 1 3 6이라면 100101의 비트마스크를 이용) 그 단계에서 선공이 이기는지 후공이 이기는지 구합니다.
그렇게 해서 cycle을 탐지하는 방식으로 구현했습니다. (base case 처리가 많이 힘들더라구요 허허)
무튼 bit연산을 이용해서 남들보다 빠를 줄 알았는데, 빠르기는 무슨 훨씬 느리네요 ㅠㅠ
그래서 궁금한 것은
1. 대부분의 사람들은 cycle을 어떻게 구하는지 궁금합니다. 배열에 dp처럼 저장해둔다음 최대 22개의 원소들을 매 단계마다 비교하면서 cycle을 찾나요? 만약 그렇다면, 시간복잡도가 (2^22+22)*22 여서 완전 간당간당한데 어떻게 이렇게 구현해도 통과할 수 있음을(즉, 시간복잡도가 괜찮음을) 판단하고 구현할 수 있을까요? 아니면 혹시 다른 빠른 방법이 있는 것인가요?
2. 제 풀이가 남들 풀이보다 느린 이유가 궁금합니다. 그나마 생각해볼 수 있는게 70~115번 줄에 있는 for문 인데, 최대가 N이라고 해도 cycle을 감지하면 반드시 빠져나오게 되어있어서 결국 상관 없을 것 같거든요. 아니면 혹시 vector할당이 너무 커서 시간이 오래걸리는 것인가요..?
ksjb2897 1년 전 1
2^22+22개 내에서 사이클이 나와야 하는데, 그러면 상수시간만에 중복되는지 확인을 해야해서 일단 bitmask느낌으로 풀었습니다.
(막 질문 글 찾아보니 사이클은 최대 500개 내로 형성된다는데, 실전에서 이 문제를 풀면 그걸 직접 구할 수는 없으니까 일단 2^22+22개라고 생각을 하고 하겠습니다,,)
무튼, 저는
선공이 이기는 경우와 후공이 이기는 경우를 매 단계마다 저장해둡니다.
그러고 매 단계마다 bit연산을 통해(예를 들어, 돌이 1 3 6이라면 100101의 비트마스크를 이용) 그 단계에서 선공이 이기는지 후공이 이기는지 구합니다.
그렇게 해서 cycle을 탐지하는 방식으로 구현했습니다. (base case 처리가 많이 힘들더라구요 허허)
무튼 bit연산을 이용해서 남들보다 빠를 줄 알았는데, 빠르기는 무슨 훨씬 느리네요 ㅠㅠ
그래서 궁금한 것은
1. 대부분의 사람들은 cycle을 어떻게 구하는지 궁금합니다. 배열에 dp처럼 저장해둔다음 최대 22개의 원소들을 매 단계마다 비교하면서 cycle을 찾나요? 만약 그렇다면, 시간복잡도가 (2^22+22)*22 여서 완전 간당간당한데 어떻게 이렇게 구현해도 통과할 수 있음을(즉, 시간복잡도가 괜찮음을) 판단하고 구현할 수 있을까요? 아니면 혹시 다른 빠른 방법이 있는 것인가요?
2. 제 풀이가 남들 풀이보다 느린 이유가 궁금합니다. 그나마 생각해볼 수 있는게 70~115번 줄에 있는 for문 인데, 최대가 N이라고 해도 cycle을 감지하면 반드시 빠져나오게 되어있어서 결국 상관 없을 것 같거든요. 아니면 혹시 vector할당이 너무 커서 시간이 오래걸리는 것인가요..?