반응형
https://www.acmicpc.net/problem/2565
2565번: 전깃줄
첫째 줄에는 두 전봇대 사이의 전깃줄의 개수가 주어진다. 전깃줄의 개수는 100 이하의 자연수이다. 둘째 줄부터 한 줄에 하나씩 전깃줄이 A전봇대와 연결되는 위치의 번호와 B전봇대와 연결되는 위치의 번호가 차례로 주어진다. 위치의 번호는 500 이하의 자연수이고, 같은 위치에 두 개 이상의 전깃줄이 연결될 수 없다.
www.acmicpc.net
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
|
#include<iostream>
#include<algorithm>
using namespace std;
struct E{
int a;
int b;
};
E e[100];
bool cmp(E&a ,E&b){
if(a.a < b.a) return true;
else return false;
}
int main(void){
int N;
int a,b;
cin>>N;
for(int n=0;n<N;n++) {
cin>>a>>b;
e[n].a =a;
e[n].b =b;
}
sort(e,e+N,cmp);
int result= 0;
int dp[100]={0,};
dp[0]=1;
for(int i=1;i<N;i++){
if(dp[i]==0) dp[i] =1;
for(int j=0;j<i;j++){
if((e[i].b > e[j].b) && (dp[i] < dp[j] +1))
dp[i] = dp[j] +1;
}
result = max(result,dp[i]);
}
cout<<N - result;
}
http://colorscripter.com/info#e" target="_blank" style="color:#4f4f4ftext-decoration:none">Colored by Color Scripter
|
반응형
'ProgramSoliving' 카테고리의 다른 글
| 백준 : 13460* (0) | 2020.01.18 |
|---|---|
| 백준 : 15685 * (0) | 2020.01.15 |
| 백준 : 2869 (0) | 2020.01.12 |
| 백준 : 17779 (0) | 2020.01.12 |
| 백준 : 14891 (0) | 2020.01.12 |