8906번 - 랩탑 다국어채점 준비 중

시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 128 MB18000.000%

문제

랩탑(노트북)은 이동하면서 사용할 수 있는 개인용 컴퓨터이다. 노트북은 디스플레이, 키보드, CD-ROM 같은 데스크탑 컴퓨터의 전형적인 부품을 모두 포함하고 있다. 랩탑의 가장 큰 특징은 휴대성이다. 즉, 집이나 사무실 말고도 커피숍, 강의실, 도서관, 미팅룸과 같은 곳에서도 자유롭게 이용할 수 있다. 랩탑은 배터리를 사용한다. 보통 배터리를 2시간에서 5시간정도 사용할 수 있으며, 에너지를 많이 사용하는 경우에는 1시간으로 줄어들 수도 있다. 배터리의 성능은 사용 기간이 오래될수록 점점 떨어진다.

일정 시간동안 랩탑을 사용하지 않으면, 에너지 소비를 줄이기 위해 대기 모드나 절전 모드로 진입한다. 이러한 모드에 진입하게 되면, 에너지를 더 이상 소비하지 않는다. 하지만, 랩탑을 다시 활성화 시키려면 단위 시간동안 특정 양만큼의 에너지가 필요하다. 따라서 랩탑의 총 에너지 소비량을 줄이려면, 사용하지 않는 구간을 줄여야 한다.

각각의 작업 Ti는 릴리즈 타임 ri와 데드라인 di를 가지고 있다. Ti는 단위 시간만큼만 실행되며, 시간 구간 [ri,di]내에 스케줄되고 완료되어야 한다. 또한 작업들은 아래와 같은 조건을 만족한다.

  1. ri와 di는 정수이고, Ti 는 정수 시간에 스케줄 되어야 한다.
  2. ri ≤ rj일 필요충분조건은 di ≤ dj이다.
  3. 모든 작업을 각각의 구간 내에 완료하는 스케줄이 적어도 하나 존재한다.

사용하지 않는 구간의 수를 최소화하면서 모든 작업을 스케줄하는 방법을 찾는 프로그램을 작성하시오. 사용하지 않는 구간은 첫 번째 작업을 스케줄한 이후부터 센다.

예를 들어, [r1,d1] = [4,8], [r2,d2] = [1,3], [r3,d3] = [8,10], [r4,d4] = [0,3], [r5,d5] = [6,8]과 같이 작업이 다섯 개 있는 경우를 생각해보자. 그림 1처럼 스케줄한 경우 사용하지 않는 구간의 수는 3개이다. 하지만, 그림 2와 같이 스케줄하면 사용하지 않는 구간은 1개이다.

그림 1. 사용하지 않는 구간이 3개인 스케줄

그림 2. 사용하지 않는 구간이 최소 개수인 스케줄

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 작업의 수 n(1 ≤ n ≤ 100,000)가 주어진다. 다음 n개 줄에는 작업 Ti의 릴리즈 시간 ri와 데드라인 di가 주어진다. (0 ≤ ri ≤ di ≤ 1,000,000)

출력

각 테스트 케이스 마다 사용하지 않는 구간의 최소 개수를 출력한다.

예제 입력 1 

2
5
4 8
1 3
8 10
0 3
6 8
9
0 4
0 4
3 6
3 6
5 7
6 8
8 11
9 11
10 11

예제 출력 1 

1
0
W3sicHJvYmxlbV9pZCI6Ijg5MDYiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWI3YTlcdWQwZDEiLCJkZXNjcmlwdGlvbiI6IjxwPlx1YjdhOVx1ZDBkMShcdWIxNzhcdWQyYjhcdWJkODEpXHVjNzQwIFx1Yzc3NFx1YjNkOVx1ZDU1OFx1YmE3NFx1YzExYyBcdWMwYWNcdWM2YTlcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWFjMWNcdWM3NzhcdWM2YTkgXHVjZWY0XHVkNGU4XHVkMTMwXHVjNzc0XHViMmU0LiBcdWIxNzhcdWQyYjhcdWJkODFcdWM3NDAgXHViNTE0XHVjMmE0XHVkNTBjXHViODA4XHVjNzc0LCBcdWQwYTRcdWJjZjRcdWI0ZGMsIENELVJPTSBcdWFjMTlcdWM3NDAgXHViMzcwXHVjMmE0XHVkMDZjXHVkMGQxIFx1Y2VmNFx1ZDRlOFx1ZDEzMFx1Yzc1OCBcdWM4MDRcdWQ2MTVcdWM4MDFcdWM3NzggXHViZDgwXHVkNDg4XHVjNzQ0IFx1YmFhOFx1YjQ1MCBcdWQzZWNcdWQ1NjhcdWQ1NThcdWFjZTAgXHVjNzg4XHViMmU0LiBcdWI3YTlcdWQwZDFcdWM3NTggXHVhYzAwXHVjN2E1IFx1ZDA3MCBcdWQyYjlcdWM5ZDVcdWM3NDAgXHVkNzM0XHViMzAwXHVjMTMxXHVjNzc0XHViMmU0LiBcdWM5ODksIFx1YzlkMVx1Yzc3NFx1YjA5OCBcdWMwYWNcdWJiMzRcdWMyZTQgXHViOWQwXHVhY2UwXHViM2M0IFx1Y2VlNFx1ZDUzY1x1YzIwZCwgXHVhYzE1XHVjNzU4XHVjMmU0LCBcdWIzYzRcdWMxMWNcdWFkMDAsIFx1YmJmOFx1ZDMwNVx1YjhmOFx1YWNmYyBcdWFjMTlcdWM3NDAgXHVhY2YzXHVjNWQwXHVjMTFjXHViM2M0IFx1Yzc5MFx1YzcyMFx1Yjg2ZFx1YWM4YyBcdWM3NzRcdWM2YTlcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YjJlNC4gXHViN2E5XHVkMGQxXHVjNzQwIFx1YmMzMFx1ZDEzMFx1YjlhY1x1Yjk3YyBcdWMwYWNcdWM2YTlcdWQ1NWNcdWIyZTQuIFx1YmNmNFx1ZDFiNSBcdWJjMzBcdWQxMzBcdWI5YWNcdWI5N2MgMlx1YzJkY1x1YWMwNFx1YzVkMFx1YzExYyA1XHVjMmRjXHVhYzA0XHVjODE1XHViM2M0IFx1YzBhY1x1YzZhOVx1ZDU2MCBcdWMyMTggXHVjNzg4XHVjNzNjXHViYTcwLCBcdWM1ZDBcdWIxMDhcdWM5YzBcdWI5N2MgXHViOWNlXHVjNzc0IFx1YzBhY1x1YzZhOVx1ZDU1OFx1YjI5NCBcdWFjYmRcdWM2YjBcdWM1ZDBcdWIyOTQgMVx1YzJkY1x1YWMwNFx1YzczY1x1Yjg1YyBcdWM5MDRcdWM1YjRcdWI0ZTQgXHVjMjE4XHViM2M0IFx1Yzc4OFx1YjJlNC4gXHViYzMwXHVkMTMwXHViOWFjXHVjNzU4IFx1YzEzMVx1YjJhNVx1Yzc0MCBcdWMwYWNcdWM2YTkgXHVhZTMwXHVhYzA0XHVjNzc0IFx1YzYyNFx1Yjc5OFx1YjQyMFx1YzIxOFx1Yjg1ZCBcdWM4MTBcdWM4MTAgXHViNWE4XHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM3N2NcdWM4MTUgXHVjMmRjXHVhYzA0XHViM2Q5XHVjNTQ4IFx1YjdhOVx1ZDBkMVx1Yzc0NCBcdWMwYWNcdWM2YTlcdWQ1NThcdWM5YzAgXHVjNTRhXHVjNzNjXHViYTc0LCBcdWM1ZDBcdWIxMDhcdWM5YzAgXHVjMThjXHViZTQ0XHViOTdjIFx1YzkwNFx1Yzc3NFx1YWUzMCBcdWM3MDRcdWQ1NzQgXHViMzAwXHVhZTMwIFx1YmFhOFx1YjRkY1x1YjA5OCBcdWM4MDhcdWM4MDQgXHViYWE4XHViNGRjXHViODVjIFx1YzljNFx1Yzc4NVx1ZDU1Y1x1YjJlNC4gXHVjNzc0XHViN2VjXHVkNTVjIFx1YmFhOFx1YjRkY1x1YzVkMCBcdWM5YzRcdWM3ODVcdWQ1NThcdWFjOGMgXHViNDE4XHViYTc0LCBcdWM1ZDBcdWIxMDhcdWM5YzBcdWI5N2MgXHViMzU0IFx1Yzc3NFx1YzBjMSBcdWMxOGNcdWJlNDRcdWQ1NThcdWM5YzAgXHVjNTRhXHViMjk0XHViMmU0LiBcdWQ1NThcdWM5YzBcdWI5Y2MsIFx1YjdhOVx1ZDBkMVx1Yzc0NCBcdWIyZTRcdWMyZGMgXHVkNjVjXHVjMTMxXHVkNjU0IFx1YzJkY1x1ZDBhNFx1YjgyNFx1YmE3NCBcdWIyZThcdWM3MDQgXHVjMmRjXHVhYzA0XHViM2Q5XHVjNTQ4IFx1ZDJiOVx1YzgxNSBcdWM1OTFcdWI5Y2NcdWQwN2NcdWM3NTggXHVjNWQwXHViMTA4XHVjOWMwXHVhYzAwIFx1ZDU0NFx1YzY5NFx1ZDU1OFx1YjJlNC4gXHViNTMwXHViNzdjXHVjMTFjIFx1YjdhOVx1ZDBkMVx1Yzc1OCBcdWNkMWQgXHVjNWQwXHViMTA4XHVjOWMwIFx1YzE4Y1x1YmU0NFx1YjdjOVx1Yzc0NCBcdWM5MDRcdWM3NzRcdWI4MjRcdWJhNzQsIFx1YzBhY1x1YzZhOVx1ZDU1OFx1YzljMCBcdWM1NGFcdWIyOTQgXHVhZDZjXHVhYzA0XHVjNzQ0IFx1YzkwNFx1YzVlY1x1YzU3YyBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YWMwMVx1YWMwMVx1Yzc1OCBcdWM3OTFcdWM1YzUgVDxzdWI+aTxcL3N1Yj5cdWIyOTQgXHViOWI0XHViOWFjXHVjOTg4IFx1ZDBjMFx1Yzc4NCByPHN1Yj5pPFwvc3ViPlx1YzY0MCBcdWIzNzBcdWI0ZGNcdWI3N2NcdWM3NzggZDxzdWI+aTxcL3N1Yj5cdWI5N2MgXHVhYzAwXHVjOWMwXHVhY2UwIFx1Yzc4OFx1YjJlNC4gVDxzdWI+aTxcL3N1Yj5cdWIyOTQgXHViMmU4XHVjNzA0IFx1YzJkY1x1YWMwNFx1YjljY1x1ZDA3Y1x1YjljYyBcdWMyZTRcdWQ1ODlcdWI0MThcdWJhNzAsIFx1YzJkY1x1YWMwNCBcdWFkNmNcdWFjMDQgW3I8c3ViPmk8XC9zdWI+LGQ8c3ViPmk8XC9zdWI+XVx1YjBiNFx1YzVkMCBcdWMyYTRcdWNmMDBcdWM5MDRcdWI0MThcdWFjZTAgXHVjNjQ0XHViOGNjXHViNDE4XHVjNWI0XHVjNTdjIFx1ZDU1Y1x1YjJlNC4gXHViNjEwXHVkNTVjIFx1Yzc5MVx1YzVjNVx1YjRlNFx1Yzc0MCBcdWM1NDRcdWI3OThcdWM2NDAgXHVhYzE5XHVjNzQwIFx1Yzg3MFx1YWM3NFx1Yzc0NCBcdWI5Y2NcdWM4NzFcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxvbD5cclxuXHQ8bGk+cjxzdWI+aTxcL3N1Yj5cdWM2NDAgZDxzdWI+aTxcL3N1Yj5cdWIyOTQgXHVjODE1XHVjMjE4XHVjNzc0XHVhY2UwLCBUPHN1Yj5pPFwvc3ViPiBcdWIyOTQgXHVjODE1XHVjMjE4IFx1YzJkY1x1YWMwNFx1YzVkMCBcdWMyYTRcdWNmMDBcdWM5MDQgXHViNDE4XHVjNWI0XHVjNTdjIFx1ZDU1Y1x1YjJlNC48XC9saT5cclxuXHQ8bGk+cjxzdWI+aTxcL3N1Yj4gJmxlOyByPHN1Yj5qPFwvc3ViPlx1Yzc3YyBcdWQ1NDRcdWM2OTRcdWNkYTlcdWJkODRcdWM4NzBcdWFjNzRcdWM3NDAgZDxzdWI+aTxcL3N1Yj4gJmxlOyBkPHN1Yj5qPFwvc3ViPlx1Yzc3NFx1YjJlNC48XC9saT5cclxuXHQ8bGk+XHViYWE4XHViNGUwIFx1Yzc5MVx1YzVjNVx1Yzc0NCBcdWFjMDFcdWFjMDFcdWM3NTggXHVhZDZjXHVhYzA0IFx1YjBiNFx1YzVkMCBcdWM2NDRcdWI4Y2NcdWQ1NThcdWIyOTQgXHVjMmE0XHVjZjAwXHVjOTA0XHVjNzc0IFx1YzgwMVx1YzViNFx1YjNjNCBcdWQ1NThcdWIwOTggXHVjODc0XHVjN2FjXHVkNTVjXHViMmU0LjxcL2xpPlxyXG48XC9vbD5cclxuXHJcbjxwPlx1YzBhY1x1YzZhOVx1ZDU1OFx1YzljMCBcdWM1NGFcdWIyOTQgXHVhZDZjXHVhYzA0XHVjNzU4IFx1YzIxOFx1Yjk3YyBcdWNkNWNcdWMxOGNcdWQ2NTRcdWQ1NThcdWJhNzRcdWMxMWMgXHViYWE4XHViNGUwIFx1Yzc5MVx1YzVjNVx1Yzc0NCBcdWMyYTRcdWNmMDBcdWM5MDRcdWQ1NThcdWIyOTQgXHViYzI5XHViYzk1XHVjNzQ0IFx1Y2MzZVx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LiBcdWMwYWNcdWM2YTlcdWQ1NThcdWM5YzAgXHVjNTRhXHViMjk0IFx1YWQ2Y1x1YWMwNFx1Yzc0MCBcdWNjYWIgXHViYzg4XHVjOWY4IFx1Yzc5MVx1YzVjNVx1Yzc0NCBcdWMyYTRcdWNmMDBcdWM5MDRcdWQ1NWMgXHVjNzc0XHVkNmM0XHViZDgwXHVkMTMwIFx1YzEzY1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjNjA4XHViOTdjIFx1YjRlNFx1YzViNCwgW3I8c3ViPjE8XC9zdWI+LGQ8c3ViPjE8XC9zdWI+XSA9IFs0LDhdLCBbcjxzdWI+MjxcL3N1Yj4sZDxzdWI+MjxcL3N1Yj5dID0gWzEsM10sIFtyPHN1Yj4zPFwvc3ViPixkPHN1Yj4zPFwvc3ViPl0gPSBbOCwxMF0sIFtyPHN1Yj40PFwvc3ViPixkPHN1Yj40PFwvc3ViPl0gPSBbMCwzXSwgW3I8c3ViPjU8XC9zdWI+LGQ8c3ViPjU8XC9zdWI+XSA9IFs2LDhdXHVhY2ZjIFx1YWMxOVx1Yzc3NCBcdWM3OTFcdWM1YzVcdWM3NzQgXHViMmU0XHVjMTJmIFx1YWMxYyBcdWM3ODhcdWIyOTQgXHVhY2JkXHVjNmIwXHViOTdjIFx1YzBkZFx1YWMwMVx1ZDU3NFx1YmNmNFx1Yzc5MC4gXHVhZGY4XHViOWJjIDFcdWNjOThcdWI3ZmMgXHVjMmE0XHVjZjAwXHVjOTA0XHVkNTVjIFx1YWNiZFx1YzZiMCBcdWMwYWNcdWM2YTlcdWQ1NThcdWM5YzAgXHVjNTRhXHViMjk0IFx1YWQ2Y1x1YWMwNFx1Yzc1OCBcdWMyMThcdWIyOTQgM1x1YWMxY1x1Yzc3NFx1YjJlNC4gXHVkNTU4XHVjOWMwXHViOWNjLCBcdWFkZjhcdWI5YmMgMlx1YzY0MCBcdWFjMTlcdWM3NzQgXHVjMmE0XHVjZjAwXHVjOTA0XHVkNTU4XHViYTc0IFx1YzBhY1x1YzZhOVx1ZDU1OFx1YzljMCBcdWM1NGFcdWIyOTQgXHVhZDZjXHVhYzA0XHVjNzQwIDFcdWFjMWNcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwIHN0eWxlPVwidGV4dC1hbGlnbjpjZW50ZXJcIj48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL2lkZWwyLnBuZ1wiIHN0eWxlPVwiaGVpZ2h0OjEzMXB4OyB3aWR0aDo1NjRweFwiIFwvPjxcL3A+XHJcblxyXG48cCBzdHlsZT1cInRleHQtYWxpZ246Y2VudGVyXCI+XHVhZGY4XHViOWJjIDEuIFx1YzBhY1x1YzZhOVx1ZDU1OFx1YzljMCBcdWM1NGFcdWIyOTQgXHVhZDZjXHVhYzA0XHVjNzc0IDNcdWFjMWNcdWM3NzggXHVjMmE0XHVjZjAwXHVjOTA0PFwvcD5cclxuXHJcbjxwIHN0eWxlPVwidGV4dC1hbGlnbjpjZW50ZXJcIj48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL2lkbGUxLnBuZ1wiIHN0eWxlPVwiaGVpZ2h0Ojg1cHg7IHdpZHRoOjU2OHB4XCIgXC8+PFwvcD5cclxuXHJcbjxwIHN0eWxlPVwidGV4dC1hbGlnbjpjZW50ZXJcIj5cdWFkZjhcdWI5YmMgMi4gXHVjMGFjXHVjNmE5XHVkNTU4XHVjOWMwIFx1YzU0YVx1YjI5NCBcdWFkNmNcdWFjMDRcdWM3NzQgXHVjZDVjXHVjMThjIFx1YWMxY1x1YzIxOFx1Yzc3OCBcdWMyYTRcdWNmMDBcdWM5MDQ8XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1Yzc1OCBcdWFjMWNcdWMyMTggVFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNzU4IFx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVjNzkxXHVjNWM1XHVjNzU4IFx1YzIxOCBuKDEgJmxlOyBuICZsZTsgMTAwLDAwMClcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWIyZTRcdWM3NGMgblx1YWMxYyBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVjNzkxXHVjNWM1IFQ8c3ViPmk8XC9zdWI+XHVjNzU4IFx1YjliNFx1YjlhY1x1Yzk4OCBcdWMyZGNcdWFjMDQgcjxzdWI+aTxcL3N1Yj5cdWM2NDAgXHViMzcwXHViNGRjXHViNzdjXHVjNzc4IGQ8c3ViPmk8XC9zdWI+XHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKDAgJmxlOyByPHN1Yj5pPFwvc3ViPiAmbGU7IGQ8c3ViPmk8XC9zdWI+ICZsZTsgMSwwMDAsMDAwKTxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0IFx1YjljOFx1YjJlNCBcdWMwYWNcdWM2YTlcdWQ1NThcdWM5YzAgXHVjNTRhXHViMjk0IFx1YWQ2Y1x1YWMwNFx1Yzc1OCBcdWNkNWNcdWMxOGMgXHVhYzFjXHVjMjE4XHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJLb3JlYW4ifSx7InByb2JsZW1faWQiOiI4OTA2IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiTGFwdG9wIiwiZGVzY3JpcHRpb24iOiI8cD5BIGxhcHRvcCwgYWxzbyBjYWxsZWQgYSBub3RlYm9vaywgaXMgYSBwZXJzb25hbCBjb21wdXRlciBmb3IgbW9iaWxlIHVzZS4gQSBsYXB0b3AgaW50ZWdyYXRlcyBtb3N0IG9mIHRoZSB0eXBpY2FsIGNvbXBvbmVudHMgb2YgYSBkZXNrdG9wIGNvbXB1dGVyLCBpbmNsdWRpbmcgYSBkaXNwbGF5LCBhIGtleWJvYXJkLCBhIENELVJPTSBkcml2ZSwgZXRjLiBOZXZlcnRoZWxlc3MsIGEgZGlzdGluY3QgZmVhdHVyZSBvZiBhIGxhcHRvcCBpcyBwb3J0YWJpbGl0eSwgd2hpY2ggbWVhbnMgdGhhdCBhIGxhcHRvcCBjYW4gYmUgdXNlZCBpbiBtYW55IHBsYWNlcyBub3Qgb25seSBhdCBob21lIGFuZCBhdCB0aGUgb2ZmaWNlLCBidXQgYWxzbyBpbiBjb2ZmZWUgc2hvcHMsIGluIGxlY3R1cmUgaGFsbHMgYW5kIGxpYnJhcmllcywgb3IgYXQgYSBtZWV0aW5nIHJvb20sIGV0Yy4gTGFwdG9wcyBhcmUgdHlwaWNhbGx5IHBvd2VyZWQgYnkgYW4gaW50ZXJuYWwgcmVjaGFyZ2VhYmxlIGJhdHRlcnkgdGhhdCBpcyBjaGFyZ2VkIHVzaW5nIGFuIGV4dGVybmFsIHBvd2VyIHN1cHBseS4gVHlwaWNhbCBiYXR0ZXJ5IGxpZmUgZm9yIHN0YW5kYXJkIGxhcHRvcHMgaXMgdHdvIHRvIGZpdmUgaG91cnMsIGJ1dCBtYXkgZHJvcCB0byBhcyBsaXR0bGUgYXMgb25lIGhvdXIgd2hlbiBkb2luZyBlbmVyZ3ktaW50ZW5zaXZlIHRhc2tzLiBBIGJhdHRlcnkgcyBwZXJmb3JtYW5jZSBncmFkdWFsbHkgZGVjcmVhc2VzIHdpdGggdGltZS48XC9wPlxyXG5cclxuPHA+VG8gcmVkdWNlIGVuZXJneSBjb25zdW1wdGlvbiwgYSBsYXB0b3AgaGFzIGEgdHJhbnNpdGlvbiB0byBhIHN0YW5kYnkgb3IgaGliZXJuYXRlIG1vZGUgaWYgaXQgaGFzIGJlZW4gaWRsZSBmb3IgYSB3aGlsZS4gSW4gdGhpcyBtb2RlLCBubyBlbmVyZ3kgaXMgY29uc3VtZWQsIGJ1dCBhIGZpeGVkIGFtb3VudCBvZiBlbmVyZ3ksIHNwZWNpZmljYWxseSwgZXF1YWwgdG8gdGhlIGVuZXJneSBjb25zdW1lZCBkdXJpbmcgYSB1bml0IHRpbWUsIGlzIHJlcXVpcmVkIHdoZW4gbW92aW5nIHRoZSBsYXB0b3AgZnJvbSB0aGUgaGliZXJuYXRlIG1vZGUgdG8gdGhlIGFjdGl2ZSBtb2RlLiBTbywgbWluaW1pemluZyB0aGUgb3ZlcmFsbCBlbmVyZ3kgY29uc3VtcHRpb24gaXMgZXF1aXZhbGVudCB0byBmaW5kaW5nIGEgc2NoZWR1bGUgdG8gbWluaW1pemUgdGhlIG51bWJlciBvZiBpZGxlIHBlcmlvZHMuJm5ic3A7PFwvcD5cclxuXHJcbjxwPkVhY2ggdGFzayBUPHN1Yj5pPFwvc3ViPiBpcyBnaXZlbiB3aXRoIGEgcmVsZWFzZSB0aW1lIHI8c3ViPmk8XC9zdWI+IGFuZCBhIGRlYWRsaW5lIGQ8c3ViPmk8XC9zdWI+LCB3aGVyZSBUPHN1Yj5pPFwvc3ViPiBpcyBleGVjdXRlZCBpbiBhIHVuaXQgdGltZSwgYW5kIGl0IHNob3VsZCBiZSBzY2hlZHVsZWQgYW5kIGNvbXBsZXRlZCB3aXRoaW4gdGhlIHRpbWUgaW50ZXJ2YWwgW3I8c3ViPmk8XC9zdWI+LGQ8c3ViPmk8XC9zdWI+XS4gQWxzbyB5b3UgY2FuIGFzc3VtZSB0aGUgZm9sbG93aW5nIGNvbmRpdGlvbnMgb24gdGhlIHByb2JsZW0gaW5zdGFuY2UgYXJlIHNhdGlzZmllZDombmJzcDs8XC9wPlxyXG5cclxuPG9sPlxyXG5cdDxsaT5yPHN1Yj5pPFwvc3ViPiBhbmQgZDxzdWI+aTxcL3N1Yj4gYXJlIGludGVnZXJzIGFuZCB0aGUgdGFza3MgVDxzdWI+aTxcL3N1Yj4gbXVzdCBiZSBzY2hlZHVsZWQgYXQgaW50ZWdyYWwgdGltZXMuPFwvbGk+XHJcblx0PGxpPnI8c3ViPmk8XC9zdWI+ICZsZTsgcjxzdWI+ajxcL3N1Yj4gaWYgYW5kIG9ubHkgaWYgZDxzdWI+aTxcL3N1Yj4gJmxlOyBkPHN1Yj5qPFwvc3ViPi48XC9saT5cclxuXHQ8bGk+VGhlcmUgaXMgYXQgbGVhc3Qgb25lIHNjaGVkdWxlIGluIHdoaWNoIGFsbCB0aGUgdGFza3MgY2FuIGJlIHNjaGVkdWxlZCBhbmQgY29tcGxldGVkIHdpdGhpbiB0aGVpciB0aW1lIGludGVydmFscy4mbmJzcDs8XC9saT5cclxuPFwvb2w+XHJcblxyXG48cD5UaGUgZ29hbCBpcyB0byBtaW5pbWl6ZSB0aGUgbnVtYmVyIG9mIGlkbGUgcGVyaW9kcyBzdWNoIHRoYXQgYWxsIHRoZSB0YXNrcyBhcmUgc2NoZWR1bGVkLiBOb3RlIHRoYXQgdGhlIGlkbGUgcGVyaW9kcyBhcmUgYXNzdW1lZCB0byBvY2N1ciBhZnRlciBhIHRhc2sgaXMgZmlyc3Qgc2NoZWR1bGVkLiZuYnNwOzxcL3A+XHJcblxyXG48cD5Gb3IgZXhhbXBsZSwgdGhlcmUgYXJlIGZpdmUgdGFza3MgVDxzdWI+aTxcL3N1Yj4gd2l0aCByZWxlYXNlIHRpbWVzIHI8c3ViPmk8XC9zdWI+IGFuZCBkZWFkbGluZXMgZDxzdWI+aTxcL3N1Yj4sIGkgPSAxLCAuLi4sIDUsIHNhdGlzZnlpbmcgdGhhdCBbcjxzdWI+MTxcL3N1Yj4sZDxzdWI+MTxcL3N1Yj5dID0gWzQsOF0sIFtyPHN1Yj4yPFwvc3ViPixkPHN1Yj4yPFwvc3ViPl0gPSBbMSwzXSwgW3I8c3ViPjM8XC9zdWI+LGQ8c3ViPjM8XC9zdWI+XSA9IFs4LDEwXSwgW3I8c3ViPjQ8XC9zdWI+LGQ8c3ViPjQ8XC9zdWI+XSA9IFswLDNdLCBhbmQgW3I8c3ViPjU8XC9zdWI+LGQ8c3ViPjU8XC9zdWI+XSA9IFs2LDhdLiBGaWd1cmUgMSBzaG93cyBhIHNjaGVkdWxlIGluIHdoaWNoIHRoZSBudW1iZXIgb2YgaWRsZSBwZXJpb2RzIGlzIDMuIEhvd2V2ZXIsIHRoZXJlIGlzIGEgc2NoZWR1bGUgd2l0aCBvbmx5IG9uZSBpZGxlIHBlcmlvZCBhcyBzaG93biBpbiBGaWd1cmUgMi4mbmJzcDs8XC9wPlxyXG5cclxuPHAgc3R5bGU9XCJ0ZXh0LWFsaWduOmNlbnRlclwiPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlc1wvaWRlbDIucG5nXCIgc3R5bGU9XCJoZWlnaHQ6MTMxcHg7IHRleHQtYWxpZ246Y2VudGVyOyB3aWR0aDo1NjRweFwiIFwvPjxcL3A+XHJcblxyXG48cCBzdHlsZT1cInRleHQtYWxpZ246Y2VudGVyXCI+RmlndXJlIDEuIEEgc2NoZWR1bGUgd2l0aCAzIGlkbGUgcGVyaW9kcy4mbmJzcDs8XC9wPlxyXG5cclxuPHAgc3R5bGU9XCJ0ZXh0LWFsaWduOmNlbnRlclwiPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlc1wvaWRsZTEucG5nXCIgc3R5bGU9XCJoZWlnaHQ6ODVweDsgdGV4dC1hbGlnbjpjZW50ZXI7IHdpZHRoOjU2OHB4XCIgXC8+PFwvcD5cclxuXHJcbjxwIHN0eWxlPVwidGV4dC1hbGlnbjpjZW50ZXJcIj5GaWd1cmUgMi4gQSBzY2hlZHVsZSB3aXRoIHRoZSBtaW5pbXVtIG51bWJlciBvZiBpZGxlIHBlcmlvZHMmbmJzcDs8XC9wPlxyXG4iLCJpbnB1dCI6IjxwPllvdXIgcHJvZ3JhbSBpcyB0byByZWFkIGZyb20gc3RhbmRhcmQgaW5wdXQuIFRoZSBpbnB1dCBjb25zaXN0cyBvZiBUIHRlc3QgY2FzZXMuIFRoZSBudW1iZXIgb2YgdGVzdCBjYXNlcyBUIGlzIGdpdmVuIGluIHRoZSBmaXJzdCBsaW5lIG9mIHRoZSBpbnB1dC4gVGhlIGZpcnN0IGxpbmUgb2YgZWFjaCB0ZXN0IGNhc2UgY29udGFpbnMgYW4gaW50ZWdlciBuKDEgJmxlOyBuICZsZTsgMTAwLDAwMCksIHRoZSBudW1iZXIgb2YgdGhlIGdpdmVuIHRhc2tzLiBJbiB0aGUgbmV4dCBuIGxpbmVzIG9mIGVhY2ggdGVzdCBjYXNlLCB0aGUgaS10aCBsaW5lIGNvbnRhaW5zIHR3byBpbnRlZ2VyIG51bWJlcnMgcjxzdWI+aTxcL3N1Yj4gYW5kIGQ8c3ViPmk8XC9zdWI+LCByZXByZXNlbnRpbmcgdGhlIHJlbGVhc2UgdGltZSBhbmQgdGhlIGRlYWRsaW5lIG9mIHRoZSB0YXNrIFQ8c3ViPmk8XC9zdWI+LCByZXNwZWN0aXZlbHksIHdoZXJlICZuYnNwOzAgJmxlOyByPHN1Yj5pPFwvc3ViPiAmbGU7IGQ8c3ViPmk8XC9zdWI+ICZsZTsgMSwwMDAsMDAwLiZuYnNwOzxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPllvdXIgcHJvZ3JhbSBpcyB0byB3cml0ZSB0byBzdGFuZGFyZCBvdXRwdXQuIFByaW50IGV4YWN0bHkgb25lIGxpbmUgZm9yIGVhY2ggdGVzdCBjYXNlLiBUaGUgbGluZSBjb250YWlucyB0aGUgbWluaW11bSBudW1iZXIgb2YgaWRsZSBwZXJpb2RzLiZuYnNwOzxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IkVuZ2xpc2gifV0=

출처

ICPC > Regionals > Asia Pacific > Korea > Asia Regional - Daejeon 2011 G번

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말

© 2023 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO

  • 사업자 등록 번호: 541-88-00682
  • 대표자명: 최백준
  • 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
  • 전화번호: 02-521-0487 (이메일로 연락 주세요)
  • 이메일: contacts@startlink.io
  • 통신판매신고번호: 제 2017-서울서초-2193 호

한국어 | English (Beta)