ACM_ICPC/2012스터디 (rev. 1.9)
- 참가자 : 김태진, 정종록, 이민규, 이진규, 남성준, 권영기
- 진행 방식에 대한 회의
- 우선 www.dovelet.com 더블릿 사용
- 오늘 푼 문제
- 숙제로 풀 문제
- 참가자 : 김태진, 정종록, 권영기, 곽병학
- 진행 방식에 대한 회의
- 풀어온 문제를 가지고 논해보고, 다음 문제를 정하는 방식.
- Programming Challenge에서 알고리즘 당 두문제 정도 풀기.
- www.dovelet.com 더블릿 옥상에서 한 문제 풀기.
- Programminc Challenge 문제에 더욱 높은 우선순위를 둠. - http://uva.onlinejudge.org/
- 금요일 까지 풀어올 문제.
import java.util.Arrays;
import java.util.Comparator;
import java.util.Scanner;
class pair {
int a;
int b;
pair(int a, int b) {
this.a = a;
this.b = b;
}
}
public class Main{
public static void main(String ar[]) {
Scanner scan = new Scanner(System.in);
int n = scan.nextInt();
pair[] p = new pair[n];
for(int i=0; i<n; i++)
p[i] = new pair(scan.nextInt()-1, scan.nextInt()-1);
Arrays.sort(p, new myCmp());
int last = p[n-1].b;
int[] ans = new int[last+1];
Arrays.fill(ans, 0, p[0].b, 0);
for(int i=0; i<n; i++) {
if(i != 0)
Arrays.fill(ans, p[i-1].b, p[i].b, ans[p[i-1].b]);
ans[p[i].b] = Math.max(ans[p[i].a] +1, ans[p[i].b-1]);
}
System.out.println(ans[last]);
/*for(int i=0; i<last+1; i++)
System.out.println(ans[i] + " ");*/
}
}
class myCmp implements Comparator<pair> {
@Override
public int compare(pair o1, pair o2) {
if(o1.b < o2.b) return -1;
else if(o1.b == o2.b) {
if(o1.a < o2.a) return -1;
else if(o1.a == o2.a) return 0;
else return 1;
}
else return 1;
}
}