nick1324 4년 전 0

반례가 뭐가 있을까요?... 왜 틀리는거죠?

일단 30의 배수가 되려면 숫자에 0이 있어야 될것이고

그리고 모든 숫자를 더해서 3의 배수이고 그것을 이제 내림차순 정렬하면 제일 큰 30으로 나눠지는 수가

되는 건 알아서 구현을 했는데 왜 맞았다고 안 뜰까요 ? ㅠ

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
void Swap(int arr[], int idx1, int idx2)
{
	int temp = arr[idx1];
	arr[idx1] = arr[idx2];
	arr[idx2] = temp;
}

int MedianOfThree(int arr[], int left, int right)
{
	int samples[3] = { left, (left + right) / 2, right };

	if (arr[samples[0]] > arr[samples[1]])
		Swap(samples, 0, 1);

	if (arr[samples[1]] > arr[samples[2]])
		Swap(samples, 1, 2);

	if (arr[samples[0]] > arr[samples[1]])
		Swap(samples, 0, 1);

	return samples[1];
}

int Partition(int arr[], int left, int right)
{
	int pIdx = MedianOfThree(arr, left, right);   // 피벗을 선택!
	int pivot = arr[pIdx];

	int low = left + 1;
	int high = right;

	Swap(arr, left, pIdx);    // 피벗을 가장 왼쪽으로 이동

	while (low <= high)    // 교차되지 않을 때까지 반복
	{
		while (pivot <= arr[low] && low <= right)//여기 부호 바꾸면 내림차순
			low++;

		while (pivot >= arr[high] && high >= (left + 1))//여기 부호바꾸면 내림차순
			high--;

		if (low <= high)    // 교차되지 않은 상태라면 Swap 실행
			Swap(arr, low, high);    // low와 high가 가리키는 대상 교환
	}

	Swap(arr, left, high);    // 피벗과 high가 가리키는 대상 교환
	return high;    // 옮겨진 피벗의 위치 정보 반환
}

void QuickSort(int arr[], int left, int right)
{
	if (left < right)
	{
		int pivot = Partition(arr, left, right);    // 둘로 나눠서 
		QuickSort(arr, left, pivot - 1);    // 왼쪽 영역을 정렬
		QuickSort(arr, pivot + 1, right);    // 오른쪽 영역을 정렬
	}
}

int main(void)
{
	int len;
	int i;
	int three = 0;
	char num[1000000];
	int num_copy[100];
	int zero_state = 0;
	scanf("%s", num);
	len = strlen(num);
	for (i = 0; i < len; i++)
	{
		num_copy[i] = num[i]-'0';
		three += num[i] - '0';
		if (num[i]-'0'== 0)
		{
			zero_state += 1;
		}
	}
	if(three%3!=0 || zero_state==0)
	{
		printf("-1\n");
		return 0;
	}
	QuickSort(num_copy, 0, len - 1);
	for (i = 0; i < len; i++)
	{
		num[i] = num_copy[i] + '0';
	}
		printf("%s\n", num);
	return 0;
}

문제

문제

출처

ICPC

반례

nick1324 4년 전 0

lokilo 4년 전 1

★ int num_copy[100]; ★

nick1324 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말