( C ) SW Expert Academy 1859번

< 문제 출처 >

 

https://swexpertacademy.com/main/code/problem/problemDetail.do?problemLevel=1&contestProbId=AV5LrsUaDxcDFAXc&categoryId=AV5LrsUaDxcDFAXc&categoryType=CODE&problemTitle=&orderBy=FIRST_REG_DATETIME&selectCodeLang=ALL&select-1=1&pageSize=10&pageIndex=1 

SW Expert Academy

 

< 잘못된 풀이 >

 

 

#include<stdio.h>

int arr[1000000];

int main(void)
{
	int T;
	scanf("%d", &T);
	int N,i,j,k,z;
	

	for (i = 0; i < T; i++)
	{
		int sum = 0, max = 0;
		scanf("%d", &N);
		for (j = 0; j < N; j++)
		{
			scanf("%d", &arr[j]);  
			if (max < arr[j])
				max = arr[j];
		}
		k = 0;
		
		for (; k<N; k++)
		{
			if (max != arr[k]) 
			{
				sum += max - arr[k];
			}
		    if (max == arr[k])
			{
				max = arr[k + 1];
				for (z = k + 1; z < N; z++)
				{
					if (max <= arr[z])
						max = arr[z];
				}
			}
			k++;

		}      
		printf("#%d %d\n", i + 1, sum);

	}
	return 0;
}

 

< 잘못된 풀이2 >

 

---테스트 케이스 10개중 7개 정답----- 
#include<stdio.h>

int arr[1000000];

int main(void)
{
	int T;
	scanf("%d", &T);
	int N,i,j,k,z;
	

	for (i = 0; i < T; i++)
	{
		int sum = 0, max = 0;
		scanf("%d", &N);
		for (j = 0; j < N; j++)
		{
			scanf("%d", &arr[j]); 
			if (max < arr[j])
				max = arr[j];
		}
		k = 0;
		
		for (; k<N; k++)
		{
			if (max != arr[k]) 
			{
				sum += max - arr[k];
			}
		    if (max == arr[k])
			{
				max = arr[k + 1];
				for (z = k + 1; z < N; z++)
				{
					if (max <= arr[z])
						max = arr[z];
				}
			}

		}      
		printf("#%d %d\n", i + 1, sum);

	}
	return 0;
}

 

위 코드가 오답인 이유는 구현의 문제가 아니라, 자료형의 크기에 관한 문제에 있습니다. 

 

< 정답 >

 

#include<stdio.h>

int arr[1000000];

int main(void)
{
	int T;
	scanf("%d", &T);
	int N,i,j,k,z;
	

	for (i = 0; i < T; i++)
	{
		long long int sum = 0, max = 0;
		scanf("%d", &N);
		for (j = 0; j < N; j++)
		{
			scanf("%d", &arr[j]);  
			if (max < arr[j])
				max = arr[j];
		}
		k = 0;
		
		for (; k<N; k++)
		{
			if (max != arr[k]) 
			{
				sum += max - arr[k];
			}
		    if (max == arr[k])
			{
				max = arr[k + 1];
				for (z = k + 1; z < N; z++)
				{
					if (max <= arr[z])
						max = arr[z];
				}
			}

		}      
		printf("#%d %lld\n", i + 1, sum);

	}
	return 0;
}

 

이익의 합을 뜻하는 sum의 자료형을 long long int로 설정해줍니다.

 

sum의 자료형을  int형으로 사용하면 안되는 이유는...

 

최대크기의 수가 나오는 경우의 수를 생각해보았을때 , N은 약 백만정도이고, 백만개의 수가 주어질 수 있습니다. 그리고 각 수의 최댓값은 1만입니다. 이 1만을 가지고 간단한 연산을 해보면 1만을 10번 더하면 10만이고, 10만을 10번 더하면 100만 이 수를 10번 더하면 1000만 이 수를 또 10번 더하면 1억이됩니다. 이런식으로 더해나갔을때 int형의 최대크기 약 20억의 끝에 금방 도달하게 될 것입니다. 즉 전혀 여유로운 값의 범위가 아니게 됩니다. 그러므로 900경이라는 충분히 여유로운 정수형 범위(크기)를 가지고 있는 long long int형을 사용하여 변수 sum을 선언해 줘야 합니다.

 

<참고>

 

long long int 는 printf 함수에서 출력시에 서식 지정자로 %lld를 사용합니다.

 

프로그래밍을 할 때는 정수 자료형의 크기를 항상 생각하고, 값의 범위를 넘어서지는 않는지 확인을 해야합니다.