글 읽기 - 푸신분 힌트좀 주시면 감사하겠습니다.

lyzqm 6년 전 0

x,y,z를 정렬한 후 N^2으로 최솟값을 찾는 방법을 사용했는데요

이 풀이가 최적값을 보장하지 않는것 같고 N^2으로 해서 시간초과에도 걸릴거 같네요

계속 생각해봐도 다른 풀이가 떠오르지 않네요ㅜㅜ

도와주세용

#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
#define INF 987654321
struct Buil {
	int x, y, z;
	int operator-(const Buil &other) {
		return (abs(x - other.x) + abs(y - other.y) + abs(z - other.z));
	}
};
int N;
Buil buil[10001];
int dp[10001][2];
int ans = INF;
int main() {
	memset(dp, 0x3f, sizeof dp);
	scanf("%d", &N);
	for (int n = 0;n < N;n++) scanf("%d%d%d", &buil[n].x, &buil[n].y, &buil[n].z);
	sort(buil, buil + N, [](Buil &a, Buil &b)->bool {
		if (a.x == b.x) {
			if (a.y == b.y) return a.z < b.z;
			return a.y < b.y;
		}
		return a.x < b.x;
	});
	for (int n = 0;n < N;n++) {
		for (int m = n + 1;m < N;m++) {
			dp[m][0] = min(dp[m][0], buil[n] - buil[m]);
		}
	}

	for (int n = 1;n < N;n++) {
		for (int m = n + 1;m < N;m++) {
			dp[m][1] = min(dp[m][1], dp[n][0] + (buil[n] - buil[m]));
			ans = min(ans, dp[m][1]);
		}
	}
	printf("%d\n", ans);
	return 0;
}

doju 6년 전 1

더 빠른 풀이가 존재하는지는 잘 모르겠지만 O(N²)의 시간복잡도로 충분히 통과할 수 있습니다.

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

푸신분 힌트좀 주시면 감사하겠습니다.

lyzqm 6년 전 0

doju 6년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말