[백준] 25945: 컨테이너 재배치 (C / C++)

문제

---

문제 링크: https://www.noj.am/25945

25945번: 컨테이너 재배치

 

 

문제 분석

---

건대 '커먼 그라운드'

요약하면, 컨테이너들이 칸마다 잔뜩 있는데

높이 차이가 거의 안 나도록 만들고 싶다는 것이다.

 

근데, 난 컨테이너고 나발이고

그냥 '땅 메우기'라고 생각하기로 했다.

부족한 부분은 메워주고, 많은 부분은 빼주면 끝 아닌가?

 

컨테이너들을 모두 합해 칸 수 N으로 나누면 평균 층을 구할 수 있다.

 

모든 컨테이너들을 고르게 분포시키면,

무조건 평균 층과 같거나 평균 층보다 위에 있을 수밖에 없다.

 

ex 1) 7÷3 => 2,
3칸 모두 2로 채워도 1개가 남음.

ex 2) 14÷3 => 4,
3칸 모두 4로 채워도 2칸이 남음.

 

필요한 것 목록.

1.  컨테이너 개수 총합, 그리고 평균.

2.  평균+1보다 위에 있는 컨테이너의 개수.

3.  평균 층보다 아래에 있는(메워야 하는) 칸의 부족한 컨테이너 개수.

 

 

자세한 풀이

---

 

 

평균층까지 채워지지 않은(부족한) 칸의 컨테이너 개수는

갚아야 할 빚으로.

 

평균 + 1 층의 컨테이너는 기간 없는 포인트로.

 

평균 + 1보다 위에 있는 컨테이너들은 곧 소멸될 포인트라고 생각하면 된다.

 

 

빚을 꼭 갚아야 하는 상황에서 소멸 포인트가 있는데, 내 포인트쓰면 손해잖아.

그럼 소멸 포인트를 우선으로 사용해서 빚을 갚으면 되겠지?

 

빚을 다 갚았거나 갚지 않아도 되는데 소멸 포인트가 남아있으면,

남은 소멸 포인트를 다 써서 사고 싶은 거 사면되겠지?

 

어쨌든 둘 다 없애야 한다는 것이 핵심이다.

 

하 비유 미쳤고~

 

 

코드 (C99 / C++)

---

C 코드

#include <stdio.h>

int N;
int arr[1000000];
int sum, avg;
int u_top, bot;

int main(){
    scanf("%d", &N);
	
	for(int i=0;i<N;i++){
        scanf("%d", &arr[i]);
        sum+=arr[i];
    }
    avg=sum/N; // 평균 층 
    
    for(int i=0;i<N;i++)
        if(arr[i]<avg) bot+=avg-arr[i]; // 부족한 칸 개수 
        else if(arr[i]>(avg+1)) u_top+=arr[i]-(avg+1); // 평균+1보다 위 
    
    if(u_top<bot) printf("%d", bot); // 평균+1 위를 투입하고도 평균+1에서 옮겨 줌.
    else printf("%d", u_top); // 평균+1 위에서 bot을 채워주고도 남아 해결해야 함.
}

C++ 코드

#include <bits/stdc++.h>
using namespace std;

int arr[1000000];
int N;
int sum, avg; // 합, 평균
int u_top, bot; // 평균+1보다 위, 평균보다 아래

int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
	cin >> N;	
    
	for(int i=0;i<N;i++){
        cin >> arr[i];
        sum+=arr[i];
    }
    
    avg=sum/N; // 평균 층.
    
    for(int i=0;i<N;i++)
        if(arr[i]<avg) bot+=avg-arr[i]; // 부족한 칸 개수.
        else if(arr[i]>avg+1) u_top+=arr[i]-(avg+1); // 평균+1보다 위 칸 개수.
        
    if(u_top<=bot) cout << bot; // 평균+1 위보다 메워야할 게 많다 -> 메우는 거 우선.
    else cout << u_top; // 평균+1 위가 메워야할 것 보다 많다. -> 위에 거 하면 자동 해결.
}