처음에 생각한 알고리즘은 데이터들을 정렬하고, (큰수) (작은수) (큰수) (작은수) (큰수) 이런식으로 정렬하기
근데 큰수 작은수 번갈아가면서 정렬할 때도, 포인트는
가장 큰수가 가장 첫번째 배열에 있으면 활용도가 낮아진다?는 것
가장 큰수는 양 옆에서 이득을 봐야하기?때문에
(중간 수(남는숫자)) (첫번째로 큰수) (첫번째로 작은수) (두번째로 큰수) (두번째로 작은수) (세번째로 큰수)
이렇게 알고리즘 구성했고 코드 짰는데
90%까지 맞다가 틀렸다!!!!!!!!!!!!!!
히든 케이스가 뭐일까ㅜㅜ
(개인적으로 일직선의 좌표? 거리? 느낌으로 생각하면 이해가 빠른 느낌이다)
틀린 코드라도
#include<iostream> #include<vector> #include<math.h> using namespace std; int main() { int n; cin >> n; vector<int> arr; arr.assign(n,0); vector<int> res; res.assign(n, 0); for (int i = 0; i < n; i++) { cin >> arr[i]; } // 1.내림차순 정렬하기 for (int i = 0; i < n; i++) { for (int j = 0; j < n - 1 - i; j++) { if (arr[j]<arr[j+1]) { //swap int temp = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = temp; } } } // 큰 수 정렬 int n_size = n / 2; int add = 1; for (int i = 0; i < n_size; i++) { // res[1,3,5,...]에 큰 수를 차례로 배치하기위해 res[i + add] = arr[i]; add++; } //작은 수 정렬 int arr_idx = n-1; for (int i = 1; i < n; i++) { if (res[i]==0) { res[i] = arr[arr_idx]; arr_idx--; } } res[0] = arr[n_size]; // 두개의 데이터의 차의 합들, 절대값 int sum = 0; for (int i = 0; i < n - 1; i++) { int temp = res[i] - res[i + 1]; sum += abs(temp); } cout << sum << endl; return 0; }
!수정했음!
내 코드상에서 히든케이스 :
3
-1 0 0
출력: 2 가 나와야 정상인데 1을 출력했음
이유는?
n이 홀수개일 때는 최선이 되는 경우의 수가 한가지가 아니였음
왜냐면 n이 홀수개일 때는 가운데에 무엇을 위치하느냐에 따라 결과값이 달라지기 때문임
가운데에 가장 큰 수를 넣을 때 결과가 가장 큰 값이 나올 수 있고,
가장 작은 수를 넣을 때 결과가 가장 큰 값이 나올 수도 있음
예를 들면,
3
1 1 2
를 넣으면 가운데에 2를 넣어야 결과가 가장 큰 값(옳은 값)이 나옴
내 코드는 항상 가운데에 가장 큰 값을 넣었기 때문에
3
1 1 2
입력값이 주어졌을 때는 OK
3
0 0 -1
입력값이 주어졌을 때는 NO 였음
수정 코드
#include<iostream> #include<vector> #include<math.h> using namespace std; int main() { int n; cin >> n; vector<int> arr; arr.assign(n,0); vector<int> res; res.assign(n, -200); for (int i = 0; i < n; i++) { cin >> arr[i]; } // 1.내림차순 정렬하기 for (int i = 0; i < n; i++) { for (int j = 0; j < n - 1 - i; j++) { if (arr[j]<arr[j+1]) { //swap int temp = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = temp; } } } // 2. 큰 수,작은 수 번갈아 배치시키기 // 홀수일때만 int sum1 = 0; if (n%2!=0) { // 홀수 -> 최선의 경우의 수가 한가지가 아님 // 작은 수 정렬 int n_size = n / 2; int add = 1; for (int i = n-1; i > n_size; i--) { // res[1,3,5,...]에 큰 수를 차례로 배치하기위해 res[add] = arr[i]; add = add + 2; } //작은 수 정렬 int arr_idx = 0; for (int i = 1; i < n; i++) { if (res[i] == -200) { // 비어있으면 채워주기 res[i] = arr[arr_idx]; arr_idx++; } } res[0] = arr[n_size]; // 두개의 데이터의 차의 합들, 절대값 for (int i = 0; i < n - 1; i++) { int temp = res[i] - res[i + 1]; sum1 += abs(temp); } } // 짝수 -> 최선의 경우의 수 한가지뿐임 // res.clear(); res.assign(n, -200); // 큰 수 정렬 int n_size = n / 2; int add = 1; for (int i = 0; i < n_size; i++) { // res[1,3,5,...]에 큰 수를 차례로 배치하기위해 res[add] = arr[i]; add=add+2; } //작은 수 정렬 int arr_idx = n-1; for (int i = 1; i < n; i++) { if (res[i]==-200) { // 비어있으면 채워주기 res[i] = arr[arr_idx]; arr_idx--; } } res[0] = arr[n_size]; // 두개의 데이터의 차의 합들, 절대값 int sum = 0; for (int i = 0; i < n - 1; i++) { int temp = res[i] - res[i + 1]; sum += abs(temp); } if (n%2!=0) { if (sum<sum1) { sum = sum1; } } cout << sum << endl; return 0; }
근데 사실 좋은 코드아님ㅋㅋㅋㅋ
귀찮아서 대충,,,,대충 틀린것만 부분부분 고쳤음
