문제
내가 가진 사탕의 수, 친구들이 받고 싶은 사탕의 수들이 주어질 때
친구들이 못 받은 사탕의 개수의 제곱만큼 분노한다
친구들의 분노의 합이 최소가 되도록 하려면 어떻게 나눠줘야할까?
생각
아이디어 1
숫자가 클 수록 제곱하면 커지므로
사탕을 많이 원하는 애들한테 먼저 사탕을 나눠주면서
전체적으로 못 받는 사탕의 수가 고르게 만들어주었다
위와 같이 만들기위해
내림차순으로 원하는 사탕의 수들을 정렬하고,
앞에서부터 한 명씩 보면서 옆에 친구와 원하는 사탕의 수와 같아질 때까지 사탕을 나눠주고,
같은 수가 되면 다시 또 옆에를 보면서, 지금까지 처리한 친구들에게 1개씩 사탕을 나눠준다
ex) 3개 11개 8개를 원할 때
11 8 6
10 8 6
9 8 6
8 8 6
7 7 6
6 6 6
5 5 5
...
이런 식으로 하면
처리해온 애들은 모두 어떠한 같은 수(tempCandy)만큼 사탕을 받고 싶어하는 상태고,
아직 안 본 애들은 자기가 처음에 원하는 만큼 사탕을 받고 싶어하는 상태가 된다!
계속 보다가 내가 나눠줄 수 있는 사탕의 수가, 처리하고 있는 애들의 수보다 적어지면
사탕을 고르게 나눠줄 수 없으니까! 보는 걸 멈추고,
처리한 애들은
사탕을 1개 씩이라도 나눠줄 수 있을 땐 (tempCandy - 1)^2,
사탕이 하나도 못 나눠줄 땐 (tempCandy)^2,
처리 안 한 애들은
(처음에 원하는 사탕 개수)^2 이 분노 수치가 된다.
주석을 추가한 코드는 아래와 같고,
더 밑에 다른 방법, 전체 코드 있어요오!
//내림차순으로 원하는 사탕의 수들을 정렬
sort(wantCandy, wantCandy + n, desc);
//j는 지금까지 처리한 친구의 수
for (int j = 0; j < n;) {
//가진 사탕이 처리한 친구 수 + 현재 보고 있는 애 수보다 많으면 == 나눠줄 수 있으면
if (haveCandy >= j + 1) {
//옆에 수랑 같아질 때 옆에 친구 보러가자
if (wantCandy[j] == wantCandy[j + 1]) {
j++;
tempCandy = wantCandy[j];
}
//처리한 친구들 다 사탕 준다!
else {
haveCandy -= j + 1;
wantCandy[j]--; //앞에 모든 배열 값 바꿈 x 현재 보는 애만 바꾸고,
tempCandy = wantCandy[j]; //tempCandy로 값 알고다니자!
}
}
//사탕을 더 나눠줄 수 없을 때
else {
for (int i = j; i >= 0; i--) {
if (haveCandy > 0) { //사탕을 1개 씩이라도 나눠줄 수 있을 땐
result += (tempCandy - 1) * (tempCandy - 1);
haveCandy--;
}
else { //사탕이 하나도 못 나눠줄 땐
result += tempCandy * tempCandy;
}
}
//처리 안 한 애들은 (처음에 원하는 사탕 개수)^2
for (int i = j + 1; i < n; i++) {
result += wantCandy[i] * wantCandy[i];
}
break;
}
}아이디어 2
위에 아이디어로 잘~ 짜면 맞았습니다!는 뜨는데
코드를 조금만 잘 못 짜면, 너무 복잡하기 때문에 엄청 많이 시도해서 겨우 맞을 수 있었다.
(오름차순으로 위에서부터 보고 내려오게 구현하면,
옆에 친구(j-1)를 본다는 생각때문에 index를 잘 못 접근하거나,
tempCandy값을 이상하게 저장하는 등 틀렸었다.)
구글링해보니까 이렇게 푼 사람은 없고,
못 받는 사탕의 개수는 항상 똑같으므로 그걸,그때그때 잘 배분하도록 구현하더라!
엄청 간단하고 코드도 깔끔했다
어떤 사람이 몇 개의 사탕을 원하는 그건 알 빠 아니고..
이 사람은 ~ 개의 사탕을 못 받고, 이 사람은 ~ 개의 사탕을 못 받고 이런식!!!
그래서 쨋든 못 받는 사탕의 개수를 잘 배분하도록 구현하는 방법으로
(부족한 사탕의 개수) / (남은 사람의 수) 의 값으로 사탕을 나눠주게 하더라고?
처음에는 왜 '남은 사람의 수'로 나누어주지? 지금 당장 보고있는 애도 나눠줘야하는데?
하고 잘 이해를 못 했었는데
(부족한 사탕의 개수) / (나눠가질 사람의 수) 로 해도 되더라!
ex) 7개의 사탕을 4명의 친구들에게 나눠줘
7/4 1개
6/3 2개
4/2 2개
2/1 2개
1,2,2,2 로 나눠줌
근데 a개 만큼 못 받게 나눠주고 싶었는데,
어떤 사람은 a개 보다 적게 원할 수도 있잖아
ex) 3개 덜 나눠줘야지~ 했는데 오 얘는 2개만 받으면 된대!
그래서 오름차순으로 정렬하고,
앞에서부터 더 많이 덜 주고 싶어도 원하는 만큼만 덜 주면서,
나중에 최대한 안 나눠줄 수 있는 만큼 안 나눠주더라! (말이 웃기네)
ex) 3개 덜 줄래? 오 근데 2개 원해? 그럼 2개만 덜 줄게!
뒤에 애들이 조금 덜 받아야지 모~!!~
tmp = min(wantCandy[i], nothaveCandy / (n - i));코드
1
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>
#include <queue>
#include <cmath>
using namespace std;
unsigned long long wantCandy[100005];
bool desc(unsigned long long a, unsigned long long b) {
return a > b;
}
int main() {
unsigned long long haveCandy, n, tempCandy;
unsigned long long result = 0;
unsigned long long tmp;
cin >> haveCandy >> n;
for (int i = 0; i < n; i++) {
cin >> tmp;
wantCandy[i] = tmp;
}
sort(wantCandy, wantCandy + n, desc);
for (int j = 0; j < n;) {
if (haveCandy >= j + 1) {
if (wantCandy[j] == wantCandy[j + 1]) {
j++;
tempCandy = wantCandy[j];
}
else {
haveCandy -= j + 1;
wantCandy[j]--;
tempCandy = wantCandy[j];
}
}
else {
for (int i = j; i >= 0; i--) {
if (haveCandy > 0) {
result += (tempCandy - 1) * (tempCandy - 1);
haveCandy--;
}
else {
result += tempCandy * tempCandy;
}
}
for (int i = j + 1; i < n; i++) {
result += wantCandy[i] * wantCandy[i];
}
break;
}
}
cout << result;
return 0;
}2
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>
#include <queue>
#include <cmath>
using namespace std;
unsigned long long wantCandy[100005];
int main() {
unsigned long long haveCandy, n;
unsigned long long result = 0, nothaveCandy = 0;
unsigned long long tmp;
cin >> haveCandy >> n;
for (int i = 0; i < n; i++) {
cin >> tmp;
wantCandy[i] = tmp;
nothaveCandy += tmp;
}
sort(wantCandy, wantCandy + n);
nothaveCandy = nothaveCandy - haveCandy;
for (int i = 0; i < n ;i++) {
tmp = min(wantCandy[i], nothaveCandy / (n - i));
result += tmp * tmp;
nothaveCandy -= tmp;
}
cout << result;
return 0;
}