kesakiyo   1년 전

조세퍼스 순열 문제라고 생각하고

세그먼트 트리를 이용, 세트먼트 트리의 루트부터 리프까지 내려가며 n번째 수를 찾는 방식으로

각 판을 시뮬레이션 하면서 k번째 자리가 몇번째로 죽는지 계산하는 방법을 이용했는데

이렇게 할 경우 시간복잡도가 O(nlogn) 이 되는데 이는 약 계산으로 1억정도 나오더라구요.

아슬아슬하게 1초에 걸리지 않을까 생각했는데 98%에서 시간초과가 나네요ㅜㅜ


푸신분들 보니까 메모리도 엄청 적게 쓰고 시간도 빠르던데...

다른알고리즘이 있는건가요?!

zych1751   1년 전

처음 시작했을때 기준으로 정확하게 몇번쨰 애가 죽는지 알 필요가 없으니깐

상대적인 위치만 알면 되서 O(n)으로 풀 수 있어요.

1 2 3 4 5 에서 2가 죽고나면

3 4 5 1 이 될껀데 이거를 다시 1 2 3 4로 생각하고 이런식으로 계속 줄여나갓어요.


rootcucu   5달 전

O(n*n) 아닌가요?

3,4,5,1 을 1,2,3,4를 만드는데,  상수시간에 되는건 아니지 않나요?

zych1751   5달 전

만약 1, 2, 3, 4, 5에서 5가 몇번째 죽는지 알고싶다고 했을때,

2가 죽고나서 3, 4, 5, 1을 1, 2, 3, 4로 바꾼다고 생각만하고(직접 바꾸지말고),

이제 1, 2, 3, 4에서 3이 몇번째 죽는지를 알면됩니다.

이 과정을 계속 반복하시면 됩니다!

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