[C] 백준 - 2437번: 저울

11월 8일(수) - 그리디 알고리즘 (2437번)

2437번: 저울

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

 

최초 생각 정리

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

 

문제점

// 수정 전

int main(void)
{
	...

	int impossible = 1;
	int possible = 0;
	for (int i = 0; i < N; i++)
	{
		possible = possible + weight[i];

		if (impossible == weight[i] || impossible == possible)
		{
			impossible++;
			continue;
		}
		else
		{
			break;
		}
	}

	printf("%d", impossible);
	return 0;
}


// 수정 후

int main(void)
{
	...

	int impossible = 1;
	//int possible = 0;
	for (int i = 0; i < N; i++)
	{
		if (impossible < weight[i])
		{
			break;
		}

		impossible = impossible + weight[i];
	}

	printf("%d", impossible);
	return 0;
}

1.

저울이 측정가능한 무게에 대한 조건을 작성하여 무게를 1씩 올리며 확인하다가,

해당 조건을 충족하지 못하는 경우 break를 걸고, break가 걸린 시점의 무게를 출력하려고했다

-> 수정

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

 

풀이

#define _CRT_SECURE_NO_WARNINGS
#pragma warning(disable: 4996)

#include <stdio.h>
#include <stdlib.h>

int weight[1001];

int compare(const void* a, const void* b)
{
	int num1 = *(int*)a;
	int num2 = *(int*)b;

	if (num1 > num2)
	{
		return 1;
	}
	else if (num1 < num2)
	{
		return -1;
	}
	else
	{
		return 0;
	}
}

int main(void)
{
	int N;
	scanf("%d", &N);

	for (int i = 0; i < N; i++)
	{
		scanf("%d", &weight[i]);
	}
	qsort(weight, N, sizeof(int), compare);

	int impossible = 1;
	int possible = 0;
	for (int i = 0; i < N; i++)
	{
		if (impossible < weight[i])
		{
			break;
		}

		impossible = impossible + weight[i];
	}

	printf("%d", impossible);
	return 0;
}

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ