9426번 - 중앙값 측정
K의 개수만큼 임시배열에 소팅을해서 넣고 그안에서 해당하는 중앙값을 구해
더했는데 예제는 답이 나오지만 틀렸다고 나옵니다
이유좀 알려 주세요
아니면 반례같은 거라도
1. 마지막 답의 범위가 어떻게 될지 생각해보세요
2. 고치셔도 시간초과가 발생할 것 같은 추측을 해 봅니다..
마지막 답의 범위라는게
N = 250,000 / K=5,000 일때는 말씀하시는 건가요?
아니요, 출력하는 값의 범위를 생각해보시라는 뜻이었습니다 (최악의 경우)
예시좀 들어주실수 있으신가요 부탁드립니다
모든 온도가 65535이고 N=250000, K = 1 인 경우 답이 뭘까요
65536*250000 이라 int 를 벗어나서
sum을 long long으로 바꿔야 하지않나요?
long long 은 %lld 를 씁니다. 그리고 시간초과가 발생할텐데, 시간복잡도가 O(N K log K) 이기 때문입니다.
그러면 어떤식으로 해야할까요?
이 문제는 그냥 풀어서는 안되고 BIT 나 STL 자료구조들을 써야 해결 가능한 문제입니다 (다른 Solution 도 있을 수 있고요)
혹시 더 궁금하시면 이 문제 관련 질문들을 찾아보거나 해당 내용을 공부해보시면 될 것 같습니다
댓글을 작성하려면 로그인해야 합니다.
hanwjdgh 7년 전
K의 개수만큼 임시배열에 소팅을해서 넣고 그안에서 해당하는 중앙값을 구해
더했는데 예제는 답이 나오지만 틀렸다고 나옵니다
이유좀 알려 주세요
아니면 반례같은 거라도