글 읽기 - 어디가 틀린지 모르겠습니다.

whgmlwp07 4년 전 0

버블정렬했을때 SWAP의 수를 구하는 문제입니다.

시간을 줄이기 위해 Merge 정렬을 사용해서 Swap의 수를 구했고 count의 자료형도 long long으로 바꿔줬는데 틀렸습니다가 나옵니다... 어디가 틀린걸까요 ㅠㅠ

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

int A[500001];
int newA[500001];
int N;
long long int count = 0;

void Display()
{
	printf("\n");
	int i;
	for (i = 1; i <= N; i++) {
		printf("%d ", A[i]);
	}
}

void MergeSort()
{
	int i, j, k;
	int size = 1;
	int starti, startj;
	while (size < N) { // 배열이 두 개이상으로 나눠질때
		starti = 1, startj = starti + size;
		k = 1;
		while (startj <= N) { // 정렬할 배열이 두 개로 나눠질때
			i = starti; // 1번 배열
			j = startj; // 2번 배열
			k = starti; // 새로운 배열
			while (i < startj && j < startj + size && j <= N) { // 한 쪽 배열을 다 쓸때까지 작은 것을 먼저 옮긴다
				if (A[i] <= A[j]) { //1번 배열이 작거나 같을 때
					newA[k++] = A[i++];
				}
				else { // 2번 배열의 값이 더 작을 때
					newA[k++] = A[j++];
					count += (startj - i); // 1번 배열에 남아있는 원소의 수 만큼 더해 준다.
				}
			}
            // 남은 것들을 마저 옮겨준다.
			while (i < startj && i <= N) { 
				newA[k++] = A[i++];
			}
			while (j < startj + size && j <= N) {
				newA[k++] = A[j++];
			}

            // 시작지점 재할당
			starti = starti + 2 * size; 
			startj = startj + 2 * size;
		}
		i = 1;
		while (i < k) { // 정렬한 것들만 원래 배열에 저장한다.
			A[i] = newA[i++];
		}

		size *= 2;
	}
}

int main()
{
	int i, j;
	scanf("%d", &N);
	for (i = 1; i <= N; i++) {
		scanf("%d", &A[i]);
	}
	

	MergeSort();
	printf("%lld", count);
	return 0;
}

ha_ram 4년 전 0

일단 이 코드로는 예제의 답도 제대로 안나옵니다.

whgmlwp07 4년 전 0

3 2 1 을 입력하면

3이 나오는데 다른 반례가 있나요?

ha_ram 4년 전 0

위의 코드 그대로 복사해서 ideone.com 사이트에서 돌려봤는데

3 2 1

입력하면 출력이 1로 나옵니다.

whgmlwp07 4년 전 1

53번째 줄

A[i] = newA[i++]; 를

A[i] = newA[i];

i++;

로 바꾸니 통과하였습니다. 감사합니다!!

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

문제

문제

출처

ICPC

어디가 틀린지 모르겠습니다.

whgmlwp07 4년 전 0

ha_ram 4년 전 0

whgmlwp07 4년 전 0

ha_ram 4년 전 0

whgmlwp07 4년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말