백준 30094 그래서 나는 사진을 그만두었다

문제

30094번: 그래서 나는 사진을 그만두었다 (acmicpc.net)

30094번: 그래서 나는 사진을 그만두었다

 

관찰

만약에 학생 k가 왼쪽에서 부터 x번째에 위치해있다면(0 <= x < N) 인물 점수y는 다음과 같다.

y = ck * x + ak * (N-1-x) = (ck-ak) * x + (N-1) * ak

다음과 같은 사실을 도출해 낼 수 있다.

1. ck-ak의 값이 같은 학생들 끼리는 순서를 바뀌어도 최종값에 영향이 가지 않는다.

증명

ck-ak = M이라하자. 그러면 인물점수는 M*k + (N-1)*ak,K = {k|k는 0 <= x < N 인 자연수} 로 정리가능하다. 

K의 모든 부분집합 S에 대해,  인물 점수의 합은 |S| * M * sum(S) + |S| * (N-1) * sum(a[s]) , (S = {s}) 이다.

(순서에 영향을 받지 않는다.)

 

2. ck-ak이 다른 학생들 끼리는 ck-ak가 작은 순대로 앞에서부터 배치한다면, 최대값이 된다.

(ck-ak가 작은 순대로 뒤에서부터 배치한다면 최솟값이 된다,)

증명

인물점수가 일차함수꼴이다. f1 : y = m1x + b1, f2 : y = m2x + b2

m1 < m2라고 하자.

만약 x1 < x2라면 사진 점수는 f1(x1) + f2(x2)인 경우와 f1(x2) + f2(x1)인 경우가 있다.

 f1(x2) = f1(x1) + d1 이라하고 f2(x2) = f2(x1) + d2 라고 하자.

m1 < m2이므로 d1 < d2이다.

f1(x1) + f2(x1) + d1 > f1(x1) + f2(x1) + d2이다.

따라서 기울기가 큰 순으로 배치해야 사진 점수가 제일 커진다.

만약에 기울기가 작은 순으로 배치한다면 사진 점수가 제일 작아진다. 최솟값은 단순히 최댓값의 역과정일 뿐이다.

 

풀이

ci - ai순으로 값들을 정렬한다.

그렇게해서 최댓값과 그 순서를 하나 저장한다.

y = ck * x + ak * (N-1-x) = (ck-ak) * x + (N-1) * ak 을 이용해 값을 구해준다.

이제 입력받은 값을 ci-ai기준으로 묶어주자.

각 ci-ai별로 값이 몇개있는지를 map을 이용해 표시해준다.

그 map의 value를 factorial한 값을 다 곱해준 값이 방법의 수이다.

관찰2에서 최솟값은 단순히 최댓값의 역과정임을 알 수 있다.

방법의 수는 최댓값을 구할 때 쓴걸 재사용한다.

배열을 reverse하고 최소값과 예시 순서를 하나 저장한다.

구한 값들을 출력한다.