skynet   2년 전

직관적으로 봐도 간단한 문제 입니다.  ( 소팅에 대한 이유를 아신다면 바로 3)으로 가면 됩니다. )

단순하게 소팅을 하고 1등부터 차근 차근 넣어주면 되는데....

-> "왜 단순 소팅하면 되는가?" 를 증명? 하겠습니다.


1. 먼저 배열을 오름차순, 내림차순 정렬을 생각해 봅시다.

a[i] <= a[i + x]   (x는 1이상의 자연수)

이를 정렬 하면

a[i] , a[i + x]

a[i + x], a[i]


2. 이에 대한 output

ansA = abs(a[i] - i) + abs(a[i + x] - (i + x))

ansB = abs(a[i + x] - i) + abs(a[i] - (i + x))

두 수를 비교해 볼까요?


먼저 a[i + x] 를 a[i] + t로 치환합니다.         (t >= 0)

ansA = abs(a[i] - i) + abs(a[i] + t - (i + x))

ansB = abs(a[i] + t - i) + abs(a[i] - (i + x))


경우의 수를 살펴보면.

a[i] - i = y라 생각하면 (y < 0)

ansA = -y + abs(y + t - x)

ansB = abs(y + t) + -y + x


여기서

y + t 가 음수일 경우

ansA = -2y - t + x

ansB = -2y - t + x

ansA = ansB


y + t가 양수일 경우

ansA = -y + abs(y + t - x)

ansB = x + t

ansA는 t - x 또는 -2y -t + x 입니다. 


(조건: y <0, x > 0, t >= 0, y + t < 0)

ansA (-2y -t + x)  와 ansB(x + t) 비교 위 조건을 적용 하면

ansA <= ansB


불만도의 합을 최소로 하는것을 출력하라 했으니

답은 오름차순 정렬을 했을때 가장 효율적인 배치라는 겁니다.


3. 그렇다면 왜 틀리는 것일까?

최악의 해에 대한 출력을 생각해 봅시다.

input
n = 500,000
a[i] = {1, 1, ..., 1}


output

0, 1, 2, ... 499,999 을 모두 더한 것이겠죠?

ans = 499999 * 500000 / 2 = 124,999,750,000
                                           int       2,147,483,647
                         unsigned int       4,294,967,295

int 형 범위를 넘어 가는 군요...

답은 -> 데이터 형의 범위가 문제였습니다....


yeongjae8066   10달 전

2번에서 값 - 인덱스니까 abs(a[i+x]-(i+x)) 아닌가요?

yeongjae8066   10달 전

y + t가 양수일 경우

ansA = -y + abs(y + t - x)

ansB = x + t

ansA는 t - x 또는 2y -t + x  입니다.    -2y+x-t 

y는 음수 임으로 

ansA <= ansB


이 부분도 다시 봐주셨으면 합니다. 

https://stats.stackexchange.com/questions/108527/re-arrange-elements-in-two-vectors-to-minimize-the-elementwise-difference-betwee

여기서 짚은 것이 더 확실한 것 같습니다

skynet   9달 전

앗.... 제가 뭐라쓴건지 이해가 안가가지구 수정좀 하면서 보겠읍니다.

skynet   9달 전

저때 무슨 생각으로 푼지 기억이 안나지만, 수정하면서 든 생각인데 랜덤한 두개의 원소의 배치를 어떻게 할건지에 대해서 접근을 하였던것 같습니다.

7 2 3 중에서

2개를 뽑을수 있는 경우의 수를 모두 뽑으면

7 2

7   3

  2 3

이렇게 되는데, 여기서 2개의 위치에 대해서 만 생각을 하였던거 같네요, ;;

2 7

3    7

  2 3

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