2018. 4. 25. 19:44, 알고리즘/BOJ
https://www.acmicpc.net/problem/1168
queue나 deque를 이용하면 O(N^2) 풀이법은 쉽게 고안해낼 수 있으나, N <= 100000인 이 문제에서는 적용할 수 없습니다. 대신 Binary indexed tree를 사용하면 되는데, 우선 해당하는 자리에 사람이 있으면 1, 제거됐으면 0이라고 해봅시다. 그러면 N=7, M=3에서 리스트는
1 1 1 1 1 1 1
1 1 0 1 1 1 1
1 1 0 1 1 0 1
1 0 0 1 1 0 1
1 0 0 1 1 0 0
1 0 0 1 0 0 0
0 0 0 1 0 0 0
0 0 0 0 0 0 0
이 될 것입니다. 배열의 시작 인덱스를 편의상 1이라고 할 때 sum(k)를 L[1]+L[2]+L[3]+..+L[k]이라고 하고, 직전에 제거된 위치가 i라고 할 때, 잘 생각해보면 그 다음에 제거될 위치는 L[j]-L[i] = M을 만족하는 가장 작은 j입니다. 저희는 이러한 sum 함수를 binary indexed tree로 O(k) 대신 O(lgN)에 계산할 수 있고, j 또한 binary search로 O(NlgN) 대신 O(lg^2N)으로 계산할 수 있습니다.
j의 범위가 선형이 아니라 원형인 점에 조금 주의해야합니다.
'알고리즘 > BOJ' 카테고리의 다른 글
[BOJ] 1305번: 광고 (0) | 2018.04.26 |
---|---|
[BOJ] 1179번: 마지막 조세퍼스 문제 (0) | 2018.04.25 |
[BOJ] 11025번: 조세퍼스 문제 3 (2) | 2018.04.25 |
[BOJ] 1040번: 정수 (2) | 2018.04.25 |
[BOJ] 1134번: 식 (0) | 2018.04.24 |
[BOJ] 1035번: 조각 움직이기 (0) | 2018.04.23 |
Comments