[백준알고리즘] 9426 (대실패, 예제용) 중앙값 측정

 

중앙값 측정

 

 

 

본 문제는 맥스 인덱스 값이 250000이나 되는데 시간제한이 1초인 문제였다. 쉬운 문제인 줄 알고 코드를 작성하기 시작했는데, 알고보니 O(nlogn)을 만족하는 알고리즘을 사용해서 푸는 고난도 문제였다... 그래서 초보자인 나는 예제 수준의 케이스만 맞출 수 있는 코드를 작성했고 ㅜㅜ 나중에 언젠가 풀어내리라 다짐했다!!

 

문제

기상학에서 주요 사용하는 대표값은 중앙값이다. (중앙값의 정의는 힌트에 나와있다)

상근이는 1초에 한 번씩 온도를 재는 기계를 가지고 있고, 이 기계에 들어갈 소프트웨어를 작성하려고 한다. 기계에는 작은 디지털 디스플레이가 하나 달려잇다. 매 초마다 디스플레이는 지난 K초동안 측정한 온도의 중앙값을 화면에 보여준다.

상근이는 소프트웨어를 기계에 올리기 전에 컴퓨터에서 테스트해보려고 한다.

총 N초 동안 측정한 온도가 주어졌을 때, 디스플레이에 표시된 중앙값의 합을 구하는 프로그램을 작성하시오. 즉, N개의 수가 주어졌을 때, 길이가 K인 연속 부분 수열 N-K+1개의 중앙값의 합을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 250,000, 1 ≤ K ≤ 5,000, K ≤ N)

둘째 줄부터 N개 줄에 측정한 온도가 순서대로 주어진다. 온도는 0보다 크거나 같고, 65535보다 작거나 같은 정수이다.

출력

길이가 K인 모든 연속 부분 수열의 중앙값의 합을 출력한다.

예제 입력

10 3
3
4
5
6
7
8
9
10
11
12

예제 출력

60

 

 

 

 

//평범한 중앙값 더하기 문제 ^^...

#include <iostream>
#include <algorithm>
using namespace std;

 

int N, K;
long long result = 0;
int deg[250000];
int mid[5000];

 

void search(int idx) //idx 맥스=7, K=3, N인덱스 9까지
{
 int val = 0, cnt = 0;

  for (int i = idx; i < idx + K; i++)
   mid[cnt++] = deg[i];

  sort(mid, mid + K);

  //1 2 3 4 면 4+1/2번째로 작은 수 = 2번째로 작은수 = 인덱스1
  //1 2 3 4 5 6 7 면 7+1/2 4번째로 작은수= 인덱스3
  val = mid[((K+1) / 2) -1];

  result += val;
  return;
}

 

void solve(int cur, int n)
{
 if (n == K)
 {
  for (int i = 0; i < K; i++)
   mid[i] = 0;

  search(cur - K);
  return;
 }

 if (n >= K) return;

 if (cur >= N) return;

 else solve(cur + 1, n + 1);

 return;
}

 

int main()
{
 scanf("%d%d", &N, &K);

 for (int i = 0; i < N; i++)
  scanf("%d", &deg[i]);

 result = 0;

 for (int i = 0; i <= N - K; i++)
  solve(i, 0);

 printf("%lld\n", result);

 return 0;
}