[백준] 13305번 문제풀이

문제 : www.acmicpc.net/problem/13305

 

알고리즘 :

1. Min보다 작은 값이 나오면, 갱신하면서 km와 cost를 곱함.

2. 만약 Min과 같은 값이 나오면, 나머지 남은 거리과 min을 곱함.

3. 이 모든 곱의 합을 출력.

 

너무너무 간단한 문제이다. 엄청 간단하게 풀 것으로 예상했고,

처음에는 1번을 생각하지 못하고, 2번만 생각해서 코딩을 하였는데,

제출 해보니 Fail이 나왔다. 그래서 TestCase를 다시 세심히 분석해보니,

1번 부분을 놓쳐서 추가를 하였다.

 

처음부터 1,2번을 생각을 했어야 했다.

알고리즘이 만들어 졌다고 성급하게 코딩을 해서는 안되는것 같다.

 

코드 :

#define _CRT_SECURE_NO_WARNINGS

#define MAX 100000

#include <stdio.h>

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

	long long int km[MAX];
	long long int cost[MAX];
	int min;
	min = 2147483647;
	long long int count = 0;
	for (int i = 0; i < n - 1; i++)
	{
		scanf(" %lld", &km[i]);
		count += km[i];
	}
	for (int i = 0; i < n; i++)
	{
		scanf(" %lld", &cost[i]);
		if (cost[i] < min && i != n - 1) { min = cost[i]; }
	}

	long long int result = 0;
	long long int temp = cost[0];
	for (int i = 0; i < n - 1; i++)
	{
		if (cost[i] == min)
		{
			result += cost[i] * count;
			break;
		}
		if (cost[i] < temp)
		{
			temp = cost[i];
		}
		result += temp * km[i];
		count -= km[i];
	}
	printf("%lld", result);

	return 0;
}

 

long long 자료형을 써주지 않아서, 계속 실패를 하였다. 이유가 뭔지 모르겠어서 구글링으로 찾아보았는데,

int a;
int b;
long long int c;

c = a*b;

나는 위의 코드가 되는줄 알았다. 하지만, a*b 를 하는 동시에 overflow가 생겨서 C에는 쓰레기 값이 들어온다는 것을 알았다. 따라서, 저 코드가 성립이 되려면 이와 같이 자료형을 통합시켜 줘야한다.

long long int a;
long long int b;
long long int c;

c = a*b;

다음부터는 이런 실수 없다.

 

걸린시간 : 84분 (알고리즘:14분, 구현 및 디버깅 : 70분)