์ธ์ ๋ ์ต๊ณ ๋ง์ ์งํฅํ๋ ๊ตด์ง์ ๋๊ธฐ์ ์ง์ ์ฃผ์ํ์ฌ๊ฐ ์ ๊ท ์ฌ์ ์ฑ์ฉ์ ์ค์ํ๋ค. ์ธ์ฌ ์ ๋ฐ ์ํ์ 1์ฐจ ์๋ฅ์ฌ์ฌ์ 2์ฐจ ๋ฉด์ ์ํ์ผ๋ก ์ด๋ฃจ์ด์ง๋ค. ์ต๊ณ ๋ง์ ์งํฅํ๋ค๋ ๊ธฐ์ ์ ์ด๋ ์ ๋ฐ๋ผ ๊ทธ๋ค์ ์ต๊ณ ์ ์ธ์ฌ๋ค๋ง์ ์ฌ์์ผ๋ก ์ ๋ฐํ๊ณ ์ถ์ด ํ๋ค.
๊ทธ๋์ ์ง์ ์ฃผ์ํ์ฌ๋, ๋ค๋ฅธ ๋ชจ๋ ์ง์์์ ๋น๊ตํ์ ๋ ์๋ฅ์ฌ์ฌ ์ฑ์ ๊ณผ ๋ฉด์ ์ํ ์ฑ์ ์ค ์ ์ด๋ ํ๋๊ฐ ๋ค๋ฅธ ์ง์์๋ณด๋ค ๋จ์ด์ง์ง ์๋ ์๋ง ์ ๋ฐํ๋ค๋ ์์น์ ์ธ์ ๋ค. ์ฆ, ์ด๋ค ์ง์์ A์ ์ฑ์ ์ด ๋ค๋ฅธ ์ด๋ค ์ง์์ B์ ์ฑ์ ์ ๋นํด ์๋ฅ ์ฌ์ฌ ๊ฒฐ๊ณผ์ ๋ฉด์ ์ฑ์ ์ด ๋ชจ๋ ๋จ์ด์ง๋ค๋ฉด A๋ ๊ฒฐ์ฝ ์ ๋ฐ๋์ง ์๋๋ค.
์ด๋ฌํ ์กฐ๊ฑด์ ๋ง์กฑ์ํค๋ฉด์, ์ง์ ์ฃผ์ํ์ฌ๊ฐ ์ด๋ฒ ์ ๊ท ์ฌ์ ์ฑ์ฉ์์ ์ ๋ฐํ ์ ์๋ ์ ์ ์ฌ์์ ์ต๋ ์ธ์์๋ฅผ ๊ตฌํ๋ ํ๋ก๊ทธ๋จ์ ์์ฑํ์์ค.
์ ๋ ฅ
์ฒซ์งธ ์ค์๋ ํ ์คํธ ์ผ์ด์ค์ ๊ฐ์ T(1 โค T โค 20)๊ฐ ์ฃผ์ด์ง๋ค. ๊ฐ ํ ์คํธ ์ผ์ด์ค์ ์ฒซ์งธ ์ค์ ์ง์์์ ์ซ์ N(1 โค N โค 100,000)์ด ์ฃผ์ด์ง๋ค. ๋์งธ ์ค๋ถํฐ N๊ฐ ์ค์๋ ๊ฐ๊ฐ์ ์ง์์์ ์๋ฅ์ฌ์ฌ ์ฑ์ , ๋ฉด์ ์ฑ์ ์ ์์๊ฐ ๊ณต๋ฐฑ์ ์ฌ์ด์ ๋๊ณ ํ ์ค์ ์ฃผ์ด์ง๋ค. ๋ ์ฑ์ ์์๋ ๋ชจ๋ 1์๋ถํฐ N์๊น์ง ๋์์ฐจ ์์ด ๊ฒฐ์ ๋๋ค๊ณ ๊ฐ์ ํ๋ค.
์ถ๋ ฅ
๊ฐ ํ ์คํธ ์ผ์ด์ค์ ๋ํด์ ์ง์ ์ฃผ์ํ์ฌ๊ฐ ์ ๋ฐํ ์ ์๋ ์ ์ ์ฌ์์ ์ต๋ ์ธ์์๋ฅผ ํ ์ค์ ํ๋์ฉ ์ถ๋ ฅํ๋ค.
๐ก ๋ ์ค ํ๋๋ผ๋ ํฌ๋ฉด ๋ถ์ ์ ์์
๐ก ์๋ฅ๋ฅผ ๊ธฐ์ค์ผ๋ก ๋ฑ์๋ฅผ ์ ๋ ฌํจ
๐ก 1,2,3,4,5 ๋ก ์ ๋ ฌ๋์ด ์์ผ๋, ๋ฉด์ ์ ๋ฐฐ์ด ์์๋๋ก ๊ฐ๋ฉด์ ์๋ณด๋ค ์์ ๋ฑ์๊ฐ ์์ผ๋ฉด cnt+1์ ํด์ฃผ๊ณ , ๊ธฐ์ค์ ์์ ์ ๋ฑ์๋ก ๊ฐฑ์ ํจ
( ์์ ์๋ ์ฌ๋๋ค์์ ๋์จ ์ต๊ณ ๋ฉด์ ๋ฑ์๋ณด๋ค ๋ ๋์์ผ์ง๋ง ํฉ๊ฒฉํ ์ ์์)
Arrays.sort(arr, new Comparator<int[]>() {
@Override
public int compare(int[] o1, int[] o2) {
return o1[0] - o2[0];
}
});
int cnt = 1;
int min = arr[0][1];
for(int i=1; i<n; i++) {
if(min > arr[i][1]) {
cnt++;
min = arr[i][1];
}
}
bw.write(cnt+"");
bw.write("\n");
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.BufferedWriter;
import java.io.OutputStreamWriter;
import java.util.Arrays;
import java.util.Comparator;
public class BOJ_1946 {
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
int tc = Integer.parseInt(br.readLine());
while(tc-->0) {
int n = Integer.parseInt(br.readLine());
int[][] arr = new int[n][2];
for(int i=0; i<n; i++) {
String[] s = br.readLine().split(" ");
arr[i][0] = Integer.parseInt(s[0]);
arr[i][1] = Integer.parseInt(s[1]);
}
Arrays.sort(arr, new Comparator<int[]>() {
@Override
public int compare(int[] o1, int[] o2) {
return o1[0] - o2[0];
}
});
int cnt = 1;
int min = arr[0][1];
for(int i=1; i<n; i++) {
if(min > arr[i][1]) {
cnt++;
min = arr[i][1];
}
}
bw.write(cnt+"");
bw.write("\n");
}
bw.flush();
}
}
์ฑ๊ณตโจ