글 읽기 - 다른 방법으로 풀 수는 없는건가요?

unilep 6년 전 0

정답은 맞았습니다.

하지만 밑의 방식으로 접근해봤는데 시간초과가 나서

입력제한을 보니 당연히 시간초과가 나는 방식이더라구요.

밑의 방식은

나무 1개 의 weight, x좌표, y좌표 를 vector<tree> 에 넣고 weight를 기준으로 오름차순 정렬합니다.

그리고 vector를 순차탐색하면서 LIS를 구하는 방법으로 해봤습니다.

아래의 방법을 개선하여 시간초과 안나게 할 수는 없을까요?

#include<iostream>
#include<cstring>
#include<algorithm>
#include<string>
#include<vector>
using namespace std;
int T, N, d[501*501], ans;
int dx[4] = { 1, -1, 0, 0 };
int dy[4] = { 0, 0, 1, -1 };
struct tree {
	int x;
	int y;
	int w;
	int z;
	tree(int x_, int y_, int w_) : x(x_), y(y_), w(w_) { z = 0; }
};
vector<tree> v;

bool cmp(const tree& a, const tree& b) {
	return a.w < b.w;
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin >> N;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			int t;
			cin >> t;
			v.push_back(tree(i, j, t));
		}
	}
	sort(v.begin(), v.end(), cmp);
	for (int i = 0; i < v.size(); i++) {
		tree& t = v[i];
		d[i] = 1;
		for (int j = 0; j < i; j++) {
			tree& t2 = v[j];
			if ((t.x == t2.x && abs(t.y - t2.y) == 1) || (t.y == t2.y && abs(t.x - t2.x) == 1)) 	d[i] = max(d[i], d[j] + 1);
		}
	}

	for (int i = 0; i < v.size(); i++) if (ans < d[i]) ans = d[i];
	cout << ans;
	
	return 0;
}

sgchoi5 6년 전 1

우선, LIS 를 구하는 알고리즘을 O(N²) 이 아닌 O(NlogN) 방식으로 해야 될 듯 합니다.

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

문제

문제

출처

ICPC

다른 방법으로 풀 수는 없는건가요?

unilep 6년 전 0

sgchoi5 6년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말