글 읽기 - 도와주세요 고수님들 ㅠㅠ

ddr04014 5년 전 0

merge sort 연습해본다고 정렬문제 아무거나 잡아서 merge sort를 어떻게든 써서 문제를 풀어봐야겠다 생각해서 코드가 많이 더럽지만 아래와 같이 짰습니다. 제출해도 계속 틀렸다고 뜨길래 질문 올려봅니다.

#include <iostream>

using namespace std;

void merge_sort(int arr[], int l, int r);
void merge(int arr[], int l, int m, int r);

const int MAX = 100;
int n;

int main() {
    cin >> n;
    
    int *a = new int[n];
    int *b = new int[n];
    
    for(int i = 0; i < n; i++) {
        cin >> a[i];
    }
    
    for(int i = 0; i < n; i++) {
        cin >> b[i];
    }
    
    merge_sort(a, 0, n-1);

    bool *check = new bool[n];
    int cur = 0;
    int curIdx = 0;
    long res = 0;
    for (int i = 0; i < n; i++) {
        cur = -1;
        for (int j = 0; j < n; j++) {
            if(!check[j] && (cur <= b[j])) {
                cur = b[j];
                curIdx = j;
            }
        }
        check[curIdx] = true;
        res += a[i] * cur;
    }
    
    cout << res;
    
    delete[] a;
    delete[] b;
    delete[] check;
}

// mergesort code
void merge_sort(int arr[], int l, int r) {
    int m = (l + r) / 2;
    
    if (l < r) {
        merge_sort(arr, l, m);
        merge_sort(arr, m+1, r);
        merge(arr, l, m, r);
    }
}

void merge(int arr[], int l, int m, int r) {
    int _l = l;
    int _m = m + 1;
    int tempIdx = l;
    int tempArr[MAX];
    while(_l <= m && _m << r) {
        if(arr[_l] < arr[_m]) {
            tempArr[tempIdx++] = arr[_l++];
        } else {
            tempArr[tempIdx++] = arr[_m++];
        }
    }
    
    if(_l <= m) {
        for(int i = _l; i <= m; i++) {
            tempArr[tempIdx++] = arr[i];
        }
    } else {
        for (int i = _m; i <= r; i++) {
            tempArr[tempIdx++] = arr[i];
        }
    }
    
    for(int i = l; i <= r; i++) {
        arr[i] = tempArr[i];
    }
}

eovh1962 5년 전 0

메인도 살짝 고쳤엉ㅅ

int main()
{
    /////
    merge_sort(a, 0, n - 1);
	merge_sort(b, 0, n - 1);
	long res = 0;
	for (int i = 0; i < n; i++) {
		res += a[i] * b[n - i - 1];
	}
    /////
}
void merge(int arr[], int l, int m, int r) {
	int _l = l;
	int _m = m + 1;
	int tempIdx = l;
	int tempArr[MAX];
	while (_l <= m && _m <= r) {
		if (arr[_l] < arr[_m]) {
			tempArr[tempIdx++] = arr[_l++];
		}
		else {
			tempArr[tempIdx++] = arr[_m++];
		}
	}

	if (_l <= m) {
		for (int i = _l; i <= m; i++) {
			tempArr[tempIdx++] = arr[i];
		}
	}
	else {
		for (int i = _m; i <= r; i++) {
			tempArr[tempIdx++] = arr[i];
		}
	}

	for (int i = l; i <= r; i++) {
		arr[i] = tempArr[i];
	}
}

ddr04014 5년 전 0

감사합니다!!

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

도와주세요 고수님들 ㅠㅠ

ddr04014 5년 전 0

eovh1962 5년 전 0

ddr04014 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말