글 읽기 - 혹시 제가 놓친게 있을까요?

malratz 4년 전 0

안녕하세요

이 문제를 LIS 방식으로 똑같이 풀고, 질문에 올라온 테스트 케이스와 예제를 통과했는데도 틀렸습니다가 뜨는데, 혹시 제가 놓친 부분이 어디일까요?

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

using namespace std;

bool orderByLeft(const pair<int,int> &l, const pair<int,int> &r) {
	return l.first<r.first;
}

int main() {
	int T,a,b;
	cin>>T;
	
	int DP[T]{0};
	
	vector<pair<int,int>> v;
	for(int i=0; i<T; i++) {
		cin>>a>>b;
		v.push_back(make_pair(a,b));
	}
	
	sort(v.begin(), v.end());
	
	int m=-1;
	for(int i=0; i<T; i++) {
		bool check=true;
		for(int j=i-1; j>=0; j--) {
			if(v[i].first>v[j].first&&v[i].second>v[j].second) {
				DP[i]=DP[j]+1;
				check=false;
				break;
			}
		}
		
		if(check) DP[i]=1;

		m=max(m, DP[i]);
	}
	
	cout<<T-m;
	
	return 0;
}

malratz 4년 전 0

1 2

2 3

3 4

4 1

5 5

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

문제

문제

출처

ICPC

혹시 제가 놓친게 있을까요?

malratz 4년 전 0

malratz 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말