[백준 10655] 마라톤1

https://www.acmicpc.net/problem/10655

10655번: 마라톤 1

#include <cstdio>
#include <cstdlib>
int N;
struct _st
{
	int x;
	int y;
}points[100000 + 10];

long long int length[100000 + 10];
long long int min = 0x7fffffff;
long long total = 0;

void input(void)
{
	scanf("%d", &N);
	for (int i = 0; i < N; i++) {
		scanf("%d %d", &points[i].x, &points[i].y);
	}
}



void get_min(void)
{

	for (int i = 0; i < N - 1; i++) {	// 두 점 사이의 거리 저장
		length[i + 1] = abs(points[i].x - points[i + 1].x) + abs(points[i].y - points[i + 1].y);
		total += length[i + 1];
	}


	for (int i = 1; i < N - 1; i++) {
		long long int tmp = total;
		int jump = i;	// 건너 뛸 인덱스
		tmp -= length[jump];
		tmp -= length[jump + 1];
		tmp += (abs(points[jump - 1].x - points[jump + 1].x) + abs(points[jump - 1].y - points[jump + 1].y));
		if (tmp < min) min = tmp;
	}
}


int main()
{
	input();
	get_min();
	printf("%lld", min);
	return 0;
}

이 문제는 사실 이렇게 코드를 짜기까지 시행착오가 있었다. 

배열의 크기 N이 그렇게 크지는 않아서 원래는 이중포문을 돌리려고 했다. 즉, 첫번째 포문에서는 건너 뛸 인덱스(i = jump)를 정하고, 두번째 포문에서는 i = 0부터  i = jump - 1 까지 더하고, i = jump - 1과 i = jump + 1일때 더하고, 마지막으로 i = jump + 1 부터 i = N - 1까지 더하는 ... 완전탐색 방식으로 구현했었다. 그런데 건너 뛸 인덱스가 될 수 있는 경우의 수는 최대 99998(100000 - 2)개 이며, 그때마다 각 점 사이의 거리를 계속 더해주는 방식이다 보니 타임아웃이 났다. 

 

 

그래서 "각 점 사이의 거리를 저장해놓고, 건너 뛴 인덱스의 점과 연결된 점들 사이의 거리만 갱신할 수는 없는지"를 생각해보았다. 

루프 한번으로 입력받은 각 점들 사이의 거리를 length[i + 1]에 저장하고(즉 i 번째 점과 i + 1 번째 점 사이의 거리를 length[i + 1]에 저장하는 방식), 거리의 총합을 total 변수에 저장했다. 

이후 새롭게 루프를 한번 더 돌면서 건너 뛸 인덱스(jump)를 지정하고, jump와 연결된 점들 사이의 거리를 제외하기 위해 i = jump - 1과 i = jump 사이의 거리를 총합에서 빼주었다. 마찬가지로 i = jump와 i = jump + 1 사이의 거리를 총합에서 빼주었다. 마지막으로 인덱스가 jump - 1인 점과 jump + 1인 점 사이의 거리를 구해 tmp 변수에 더해주었다. 

 

이 문제도 모든 점 사이의 거리를 더했을 때 int 범위를 벗어날 수 있으므로 출력은 "%lld"로 하는 것이 필요하다. 

타입을 반드시 고려해야하는구나.. 라고 반성한 문제..