poketred12   5년 전

맨 처음에 이 문제를 봤을 때 Persistent Segment Tree 로 풀 수 있을거라 생각해서.. 이제 PST 연습도 해볼겸 해봤는데,

최적화의 문제인지, 세그먼트 트리의 소스가 문제인지, 알기가 힘들어서 질문을 작성해봅니다.

일단은 세그먼트 트리를 활용해서 색깔이 낮은 정점부터 쿼리를 해결하는 방식으로 풀긴 했는데,

PST  로도 해볼려했으나...시간초과 문제가 계속 떠서 스트레스만 받네요...

해결한 방식도 1800ms 라 아슬아슬하긴 했네요..


https://www.acmicpc.net/source...

koosaga   5년 전

코드가 안 보여요

poketred12   5년 전

죄송합니다 공개로 돌렸습니다 ㅠㅠ

isku   5년 전

저두 PST로는 시간초과가 떠요 ..

제 코드는 더이상 어떻게 최적화할지 모르겠네요

재귀를 반복문으로 바꾼다면 흠 시간안에 들어올지 모르겠어요 ㅜ.ㅜ

시간복잡도만 보면  PST가 더빠른데 상수시간 문제인지.. 머지소트트리가 더 빠르네요 

JAVA ㅜㅜ.

poketred12   5년 전

isku 님 반가워요.. 흐음 이렇게 시간 추가로 안주는 문제들은 확실히 최적화랑 시간복잡도를 더 신경써야겠군요 ㅠㅠ

자바로 알고리즘 푸는 사람 중 한명으로써 화이팅하져 ㅠ

저는 그럼 머지소트 트리를 공부해바야겟군여 ㅎㅎㅎ

koosaga   5년 전

자바를 안 써서 잠시 기억이 안 났는데 BOJ 자바가 일반적인 자바보다 경험상 3~5배 정도 느립니다. 언어 자체의 문제가 아니라 사이트 상의 문제입니다 (이유는 운영자 분도 잘 모릅니다.)


고로 제한이 큰 문제나, 연산이 많은 문제들을 여기서 풀기는 쉽지 않습니다.

poketred12   5년 전

감사합니다 :)

isku   5년 전

Java 재채점 이후로 PST 코드가 통과되었어요

제 코드는 시간초과인 줄 알았는데 틀렸습니다로 바뀌어 있네요

아마 Java 채점에도 어느정도 문제가 있었던 것 같아요!? ㅎㅎ

오예~

poketred12   5년 전

헐 진짜네요 ㅎㅎㅎㅎㅎㅎㅎ

나이스~~~

poketred12   5년 전

근데 자바 메모리 많이 줄었나보네요 푼 문제 대략 50문제가 메모리떄문에 틀려있네요

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