coci 2009/2010

#CONTEST 1

 

BOJ 2923. 숫자게임

 

잘 생각해보면 지금까지 입력받은 A와 B를 하나는 오름차순 다른 하나는 내림차순으로 정렬하고 순서에 맞게 쌍을 짝지어주면 된다. 이 아이디어를 바로 구현하면 정렬에 필요한 시간 $O(NlogN)$ 이고 전체 시간복잡도는 $O(N^2logN)$ 가 되어 TLE가 뜰 것이다. 문제를 다시 읽어보면 입력받는 숫자는 1부터 100까지의 숫자이다. 이 점을 잘 이용해야 한다.

 

배열 2개를 만들자. a[100]과 b[100]이다.

$a[i]$ : A에 추가된 숫자 i의 개수

$b[i]$ : B에 추가된 숫자 i의 개수

투 포인터($i$, $j$)로 a는 1부터($i$) b는 100부터($j$) 차례대로 내려오면서 개수를 잘 가지고 놀면된다.

예를 들어 $v1=a[i]$ ,  $v2=b[j]$ 일 때 $v1>0  & v2>0$ 가 만족한다고 하자. 그럼 $i+j$ 값으로 $ans$을 update하고

$v1$과 $v2$ 중의 대소를 비교하여 (WLOG. $v1 > v2$)

$a[i]-=v2$ 와 $j++$ 을 수행한다. 이런식으로 탐색을 계속해나가면 된다.