글 읽기 - C++ 다이나믹 프로그래밍으로 풀었는데 시간초과가 나옵니다.

wltjd666 2년 전 0

다음과 같은 방식으로 dp를 이용해 풀었습니다.

풀이는 맞는 거 같은데 시간초과가 나옵니다. 아무래도 이중으로 loop를 돌다보니 그런거 같은데 다른 방법이 생각나지 않습니다.

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main()
{
	cin.tie(0);
	ios_base::sync_with_stdio(false);

	int n;
	cin >> n;
	
	vector<pair<unsigned int, unsigned int>> meetings(n);
	for (int i = 0; i < n; i++)
	{
		unsigned int from, to;
		cin >> from >> to;
		meetings[i] = { from, to };
	}

	sort(meetings.begin(), meetings.end(),
		[](const auto& a, const auto& b)
		{
			if (a.first == b.first)
				return a.second < b.second;
			return a.first < b.first;
		});
	
	vector<int> dp(n, 1);	
	for (int i = 1; i < n; i++)
	{
		for (int j = 0; j < i; j++)
		{
			if (meetings[i].first >= meetings[j].second)
			{
				dp[i] = max(dp[i], dp[j] + 1);
			}
		}
	}

	int max_value = 0;
	for (int e : dp) max_value = (max_value < e) ? e : max_value;
	cout << max_value << "\n";
}

shjohw12 2년 전 0

시간 복잡도가 O(N^2)이기 때문에 시간초과가 발생할 수 밖에 없습니다

wltjd666 2년 전 0

해결했습니다. 일단 정렬 방식부터 잘못되었구요. 그리고 N^2이 아니고 N 시간으로 이전 값과 현재값을 비교하면서 해서 빠른 시간에 해결할 수 있었습니다.

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

문제

문제

출처

ICPC

C++ 다이나믹 프로그래밍으로 풀었는데 시간초과가 나옵니다.

wltjd666 2년 전 0

shjohw12 2년 전 0

wltjd666 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말