Usa selfish/곽병학 - Revision history

imported>jereneal20 at 16:44, 14 August 2012

2012-08-14T16:44:11Z

← Older revision		Revision as of 16:44, 14 August 2012
Line 54:		Line 54:
	}		}
	}		}
			----
			[[ACM_ICPC/2012스터디]]

imported>molid7 at 06:22, 14 August 2012

2012-08-14T06:22:45Z

← Older revision		Revision as of 06:22, 14 August 2012
Line 39:		Line 39:

	System.out.println(ans[last]);		System.out.println(ans[last]);
	~~/*for(int i=0; i<last+1; i++)~~
	~~System.out.println(ans[i] + " ");*/~~

	}		}
Line 46:		Line 44:

	class myCmp implements Comparator<pair> {		class myCmp implements Comparator<pair> {

	~~@Override~~
	public int compare(pair o1, pair o2) {		public int compare(pair o1, pair o2) {
	if(o1.b < o2.b) return -1;		if(o1.b < o2.b) return -1;

imported>trailblaze at 06:21, 14 August 2012

2012-08-14T06:21:15Z

← Older revision		Revision as of 06:21, 14 August 2012
Line 1:		Line 1:
	=== 풀이 ===		=== 풀이 ===
	~~[[usa_selfish/권영기]]~~
	import java.util.Arrays;		import java.util.Arrays;
	import java.util.Comparator;		import java.util.Comparator;

imported>molid7 at 06:19, 14 August 2012

2012-08-14T06:19:43Z

New page

=== 풀이 ===
[[usa_selfish/권영기]]
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;
}
}