[백준 2262] 토너먼트 만들기

www.acmicpc.net/problem/2262

2262번: 토너먼트 만들기

그리디 알고리즘

첨에 우선순위큐를 쓰려했는데 위치가 고정이라 힘들것 같아서 단순 배열을 사용했다.

 

로직은 이렇다.

가장 큰 등수인 n부터 양쪽을 살펴서 차이가 작은 쪽을 택해서 그 차를 정답에 더하는 것이다.

그리고 나서 가장 큰 등수는 팝해준다.

#include <stdio.h>
#include <queue>

using namespace std;

int n;
int arr[256];

int main(void)
{
  scanf("%d", &n);
  for (int i = 0; i < n; i++)
  {
    scanf("%d", &arr[i]);
  }

  int res = 0;
  int sze = n;

  for (int i = n; i > 1; i--)
  {
    int mi = 0;
    for (int j = 0; j < sze; j++)
    {
      if (arr[j] == i)
      {
        mi = j;
        break;
      }
    }
    if (mi == 0)
    {
      res += i - arr[1];
    }
    else if (mi == sze - 1)
    {
      res += i - arr[sze - 2];
    }
    else
    {
      res += (arr[mi - 1] > arr[mi + 1]) ? i - arr[mi - 1] : i - arr[mi + 1];
    }
    sze--;
    for (int i = mi; i < sze; i++)
    {
      arr[i] = arr[i + 1];
    }
  }
  printf("%d\n", res);

  return 0;
}