PS 일지 (2)

마지막 수정 시각: 2022-12-30 16:38:54

적당히 플레 중하위권 난이도의 문제들을 풀었다.

BOJ 26268

쿼리를 \(t-x\) 순으로 정렬하고 나면, LIS와 비슷한 방식으로 \(O(NlogN)\) 에 문제를 해결할 수 있다. 이런 형태의 DP를 세그먼트 트리로 최적화하는 문제는 많이 풀어봐서 비교적 쉽게 해결했다.

BOJ 26270

헤매면 안 될 것 같은 문제인데 엄청 헤맸다.. 처음 발상이 틀리지 않았는데 미묘하게 잘못 생각한 포인트에서 그 잘못 생각한 핀트를 못 잡아서 망했다. 요즘 이런 일이 좀 잦은 것 같아서 걱정. 풀이 디테일을 왜 자꾸 잘못 생각하는지 모르겠다. 결국 좀 별로인 sqrt decomposition으로 풀긴 했지만 찝찝한 \(O(QsqrtN)\)으로 풀었다.

굳이 온라인으로 풀려고 한게 문제였던 것 같다. 오프라인 쿼리로 접근할 경우, \(l\) 이상 지점에 대해 \(length_l\)들을 \(l+length_l\)에다가 저장해두면 세그먼트 트리로 \(O(logN)\)에 쿼리의 답을 구할 수 있다. 비슷한 패턴의 문제를 종종 봤는데 왜 생각을 못했는지..

BOJ 25549

풀이 방향은 금방 정했는데 디테일한 구현에서 실수를 너무 많이 했다. set으로 구간을 합치면서 관리하는 문제를 여러번 풀어봤는데도.. 매번 애를 먹는 듯. 더 쉬운 풀이 방법이 있을 것 같은데 고민을 좀 해봐야할 것 같다.

set으로 구간을 합치는 경우는 각 정점 \(v\)에 대해 \(set_v\) 를 \(v\)의 서브트리에서 연속한 수들을 구간으로 묶어 관리한 것으로 정의하면 small to large 테크닉을 이용해 \(O(Nlog^2N)\) 시간에 문제를 해결할 수 있다.

BOJ 25544

각 점을 기준으로 좌우를 나눠서 각각 LIS, LDS를 구해 더해주면 풀 수 있다. 같은 x값을 가지는 좌표들을 좀 주의해서 처리해줄 필요는 있음. 다행히 풀이도 빨리 생각했고 구현도 잘 했다.

BOJ 25548

한참 고민하다 못 풀고 풀이를 봤다. 답 유도에 필요한 관찰은 다 했는데, 마지막에 개수를 빠르게 세는 방법은 풀이를 안 봤으면 생각 못 했을 것 같다.

답을 성립하게 하는 \(A,B,C\) 쌍의 개수를 구한다고 생각하면, 이를 문제 조건에 의해 \((A, C/A, B/C)\) 형태로 생각할 수 있다. 이 값을 전부 곱해서 \(N\)이하여야하는 조건을 기준으로 생각하면 제일 작은 값부터 순회할 때 구현을 아주 빠르고 단순하게 할 수 있다. 이런 식으로 개수를 세는 건 해본적이 없었는데 굉장히 유용한 발상같다.

BOJ 17410

거의 똑같은 문제가 있고 그걸 예전에 풀었었는데, 미묘한 제한 차이 때문에 해당 코드가 이 문제에서는 TLE가 날 것 같아서 미뤄두고 있었다. 근데 다이아 이상을 199개 푼 상태길래 200개 맞추고 싶어서 이걸 잡음.

생각 외로 조금만 상수 최적화를 해주니 풀렸다. 원래 풀이는

sqrt decomposition 해서 구간마다 해당 구간에 속한 수들을 정렬한 채로 들고 있는다
각 버킷에서 이분탐색을 통해 k보다 큰 애들 개수를 센다
업데이트 되면 원래 수 제거하고 새거 넣어서 재정렬한다

식으로 동작했다. 이 때 세번째 재정렬 과정을 굳이 sort로 할 필요가 없었는데(제거하고, 넣어야 할 위치에 넣기) 이걸 sort로 하고 있었어서 이 부분을 바꿨다. 이러면 업데이트 쿼리는 \(O(sqrtN)\)으로 최적화가 되므로, \(logN\)이 추가로 붙는 버킷 개수를 줄이는 편이 이득이 된다.

그래서 원래보다 적당히 버킷 크기를 키우는 것까지 적용했더니 원래 코드보다 2배쯤 빨라져서 그걸 제출해서 맞았다.

농 위키