기술 블로그

2878번 캔디캔디 본문

알고리즘 문제/BOJ

2878번 캔디캔디

parkit 2020. 3. 27. 17:00
728x90
반응형

https://www.acmicpc.net/problem/2878



복습 생각 Greedy 그리디 탐욕 논리 필수 추천



어려운 문제였다. 


아래는 생각한 과정


1. 이분 탐색으로 해결하려 했으니, 생각해보니 mid의 기준을 정하는 것도 어려웠다. 사실 mid로 정할만한 것도 없는 것 같다.

2. 단순 정렬 후 앞에서부터 그냥 m을 각 원소에 맞게 빼면서 계산하면 되지 않을까 싶었는데 알고보니 이게 최적이 아니였다.

3. 몇 시간 동안 막히다가 결국 다른 분의 설명과 코드를 참고하였다. 참고한 블로그 - https://lyzqm.blogspot.com/2017/08/2878.html



무작정 정렬 후 앞에서부터 m을 깎는 것이 아니다.


예를 들어, m이 10이고, 캔디를 받을 사람이 3명이고 각각 1, 2, 11개의 사탕을 원한다고 하자.


1
2
3
4
10 3
1
2
11
cs



정렬을 하면, 1 2 11이 될 것이고


10 - 1 = 9

9 - 2 = 7


이처럼 첫 번째, 두 번째 사람에겐 캔디를 모두 다 주면 7개가 남는다.


그리고 세 번째 사람에게 7개를 다 주어도 4개를 못 받기 때문에 분노는 4^2 = 16이 된다.


하지만 생각해보자.


한 사람에게만 몰두한다면 제곱이므로 숫자가 엄청 커질 것이다.


못 받는 사탕의 개수를 분배하면 어떨까?



위의 예제를 다시 생각해보자.


총 가지고 있는 사탕의 개수는 10개이고, 사람들이 원하는 사탕의 개수의 합은 14이다.


즉, 부족한 사탕은 정해져있다. 14 - 10 = 4개.(내 코드에서는 sum이 부족한 사탕의 개수)



부족한 사탕의 개수인 4개를 적절하게 배분하면 된다.


즉, 사탕을 많이 요구한 사람에게는 더 많이 주도록 한다. → 남은 사람으로 나누어 준다.((n-i)로 나누어 준다.)



rmd = (부족한 사탕의 개수) / (남은 사람의 수)


rmd는 해당 번째의 사람이 못 받는 사탕의 개수이다.











1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include<bits/stdc++.h>
 
using namespace std;
 
#define LL long long
 
int n;
LL m;
vector<LL> v;
 
int main()
{
    //freopen("C:\\Users\\park7\\Desktop\\buba.in.6", "r", stdin);
    cin.tie(0);
 
    scanf("%lld %d"&m, &n);
 
    LL input, sum = -m;
    for (int i = 0; i < n; i++) {
        scanf("%lld"&input);
        v.push_back(input);
        sum += input;
    }
 
    sort(v.begin(), v.end());
 
    LL answer = 0;
    for (int i = 0; i < n; i++) {
        LL rmd = min(v[i], sum / (n - i));
        answer += rmd*rmd;
        sum -= rmd;
    }
    
    printf("%lld\n", answer);
 
    return 0;
}
cs










728x90
반응형

'알고리즘 문제 > BOJ' 카테고리의 다른 글

18428번 감시 피하기  (0) 2020.03.29
18405번 경쟁적 전염  (0) 2020.03.27
2493번 탑  (0) 2020.03.25
1103번 게임  (0) 2020.03.25
3114번 사과와 바나나  (0) 2020.03.25