7344번 - 나무 막대 다국어

시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 128 MB49619815841.799%

문제

목공소에 n개의 나무 막대가 있고, 각 막대의 길이와 무게가 주어져 있습니다. 이 막대들은 기계를 이용해 하나 하나 가공 처리 과정을 거치게 됩니다. 이때, 각 막대를 처리할 수 있도록 기계를 준비시키는 시간, 즉 기계의 작동 준비 시간(setup time) 이라는 것이 존재합니다. 이 작동 준비 시간은 다음과 같이 부여됩니다.

  1. 첫 막대를 가공할 때 드는 작동 준비 시간은 1분입니다.
  2. 길이 l과 무게 w인 막대를 가공한 직후, 다음 가공할 막대의 길이 l'과 무게 w'에 대하여 l ≤ l' and w ≤ w' 이라면 작동 준비 시간이 들지 않습니다. 그렇지 않다면 기계가 사용하는 도구를 바꾸어야 하기 때문에 1분의 작동 준비 시간이 필요합니다.

n개의 나무 막대들의 길이와 무게가 주어졌을 때, 이 막대들을 모두 가공할 때 필요한 최소한의 작동 준비 시간을 구해야 합니다. 예를 들어, (4,9), (5,2), (2,1), (3,5), (1,4) 의 5개 나무 막대를 가공해야 한다고 해 봅시다. 만약 (1,4), (3,5), (4,9), (2,1), (5,2) 의 순서대로 가공한다면 총 2분의 작동 준비 시간이 필요하겠고, 이 경우가 최소이므로 답은 2가 되겠지요?

입력

첫째 줄에 테스트 케이스의 개수 T가 주어집니다.

각 테스트 데이터는 두 줄에 걸쳐 주어집니다. 첫째 줄에는 나무 막대의 개수 n (1 ≤ n ≤ 5000) 이 주어지고, 다음 줄에  l1, w1, l2, w2, ... ,ln, wn  (각 막대의 길이와 무게를 뜻하고, 10000을 넘지 않는 정수입니다) 가 공백을 두고 차례로 주어집니다.

출력

각 테스트 케이스별로 필요한 최소 작동 준비 시간을 한 줄에 걸쳐 출력합니다.

예제 입력 1 

3
5
4 9 5 2 2 1 3 5 1 4
3
2 2 1 1 2 2
3
1 3 2 2 3 1

예제 출력 1 

2
1
3
W3sicHJvYmxlbV9pZCI6IjczNDQiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWIwOThcdWJiMzQgXHViOWM5XHViMzAwIiwiZGVzY3JpcHRpb24iOiI8cD5cdWJhYTlcdWFjZjVcdWMxOGNcdWM1ZDAgblx1YWMxY1x1Yzc1OCBcdWIwOThcdWJiMzQgXHViOWM5XHViMzAwXHVhYzAwIFx1Yzc4OFx1YWNlMCwgXHVhYzAxIFx1YjljOVx1YjMwMFx1Yzc1OCBcdWFlMzhcdWM3NzRcdWM2NDAgXHViYjM0XHVhYzhjXHVhYzAwIFx1YzhmY1x1YzViNFx1YzgzOCBcdWM3ODhcdWMyYjVcdWIyYzhcdWIyZTQuIFx1Yzc3NCBcdWI5YzlcdWIzMDBcdWI0ZTRcdWM3NDAgXHVhZTMwXHVhY2M0XHViOTdjIFx1Yzc3NFx1YzZhOVx1ZDU3NCZuYnNwO1x1ZDU1OFx1YjA5OCBcdWQ1NThcdWIwOTggXHVhYzAwXHVhY2Y1IFx1Y2M5OFx1YjlhYyBcdWFjZmNcdWM4MTVcdWM3NDQgXHVhYzcwXHVjZTU4XHVhYzhjIFx1YjQyOVx1YjJjOFx1YjJlNC4gXHVjNzc0XHViNTRjLCBcdWFjMDEgXHViOWM5XHViMzAwXHViOTdjIFx1Y2M5OFx1YjlhY1x1ZDU2MCBcdWMyMTggXHVjNzg4XHViM2M0XHViODVkIFx1YWUzMFx1YWNjNFx1Yjk3YyBcdWM5MDBcdWJlNDRcdWMyZGNcdWQwYTRcdWIyOTQgXHVjMmRjXHVhYzA0LCBcdWM5ODkmbmJzcDtcdWFlMzBcdWFjYzRcdWM3NTggXHVjNzkxXHViM2Q5IFx1YzkwMFx1YmU0NCBcdWMyZGNcdWFjMDQoc2V0dXAgdGltZSkgXHVjNzc0XHViNzdjXHViMjk0IFx1YWM4M1x1Yzc3NCBcdWM4NzRcdWM3YWNcdWQ1NjlcdWIyYzhcdWIyZTQuIFx1Yzc3NCBcdWM3OTFcdWIzZDkgXHVjOTAwXHViZTQ0IFx1YzJkY1x1YWMwNFx1Yzc0MCBcdWIyZTRcdWM3NGNcdWFjZmMgXHVhYzE5XHVjNzc0IFx1YmQ4MFx1YzVlY1x1YjQyOVx1YjJjOFx1YjJlNC48XC9wPlxyXG5cclxuPG9sPlxyXG5cdDxsaT5cdWNjYWIgXHViOWM5XHViMzAwXHViOTdjIFx1YWMwMFx1YWNmNVx1ZDU2MCBcdWI1NGMgXHViNGRjXHViMjk0IFx1Yzc5MVx1YjNkOSBcdWM5MDBcdWJlNDQgXHVjMmRjXHVhYzA0XHVjNzQwIDFcdWJkODRcdWM3ODVcdWIyYzhcdWIyZTQuPFwvbGk+XHJcblx0PGxpPlx1YWUzOFx1Yzc3NCBsXHVhY2ZjIFx1YmIzNFx1YWM4YyB3XHVjNzc4IFx1YjljOVx1YjMwMFx1Yjk3YyBcdWFjMDBcdWFjZjVcdWQ1NWMgXHVjOWMxXHVkNmM0LCBcdWIyZTRcdWM3NGMgXHVhYzAwXHVhY2Y1XHVkNTYwIFx1YjljOVx1YjMwMFx1Yzc1OCBcdWFlMzhcdWM3NzQgbCYjMzk7XHVhY2ZjIFx1YmIzNFx1YWM4YyB3JiMzOTtcdWM1ZDAgXHViMzAwXHVkNTU4XHVjNWVjIGwgJmxlOyBsJiMzOTsgYW5kIHcgJmxlOyB3JiMzOTsgXHVjNzc0XHViNzdjXHViYTc0IFx1Yzc5MVx1YjNkOSBcdWM5MDBcdWJlNDQgXHVjMmRjXHVhYzA0XHVjNzc0IFx1YjRlNFx1YzljMCBcdWM1NGFcdWMyYjVcdWIyYzhcdWIyZTQuIFx1YWRmOFx1YjgwN1x1YzljMCBcdWM1NGFcdWIyZTRcdWJhNzQgXHVhZTMwXHVhY2M0XHVhYzAwIFx1YzBhY1x1YzZhOVx1ZDU1OFx1YjI5NCBcdWIzYzRcdWFkNmNcdWI5N2MgXHViYzE0XHVhZmI4XHVjNWI0XHVjNTdjIFx1ZDU1OFx1YWUzMCBcdWI1NGNcdWJiMzhcdWM1ZDAgMVx1YmQ4NFx1Yzc1OCBcdWM3OTFcdWIzZDkgXHVjOTAwXHViZTQ0IFx1YzJkY1x1YWMwNFx1Yzc3NCBcdWQ1NDRcdWM2OTRcdWQ1NjlcdWIyYzhcdWIyZTQuPFwvbGk+XHJcbjxcL29sPlxyXG5cclxuPHA+blx1YWMxY1x1Yzc1OCBcdWIwOThcdWJiMzQgXHViOWM5XHViMzAwXHViNGU0XHVjNzU4IFx1YWUzOFx1Yzc3NFx1YzY0MCBcdWJiMzRcdWFjOGNcdWFjMDAgXHVjOGZjXHVjNWI0XHVjODRjXHVjNzQ0IFx1YjU0YywgXHVjNzc0IFx1YjljOVx1YjMwMFx1YjRlNFx1Yzc0NCBcdWJhYThcdWI0NTAgXHVhYzAwXHVhY2Y1XHVkNTYwIFx1YjU0YyBcdWQ1NDRcdWM2OTRcdWQ1NWMgXHVjZDVjXHVjMThjXHVkNTVjXHVjNzU4IFx1Yzc5MVx1YjNkOSBcdWM5MDBcdWJlNDQgXHVjMmRjXHVhYzA0XHVjNzQ0IFx1YWQ2Y1x1ZDU3NFx1YzU3YyBcdWQ1NjlcdWIyYzhcdWIyZTQuIFx1YzYwOFx1Yjk3YyBcdWI0ZTRcdWM1YjQsICg0LDkpLCAoNSwyKSwgKDIsMSksICgzLDUpLCAoMSw0KSBcdWM3NTggNVx1YWMxYyZuYnNwO1x1YjA5OFx1YmIzNCBcdWI5YzlcdWIzMDBcdWI5N2MgXHVhYzAwXHVhY2Y1XHVkNTc0XHVjNTdjIFx1ZDU1Y1x1YjJlNFx1YWNlMCBcdWQ1NzQgXHViZDA1XHVjMmRjXHViMmU0LiBcdWI5Y2NcdWM1N2QmbmJzcDsoMSw0KSwgKDMsNSksICg0LDkpLCAoMiwxKSwgKDUsMikgXHVjNzU4IFx1YzIxY1x1YzExY1x1YjMwMFx1Yjg1YyBcdWFjMDBcdWFjZjVcdWQ1NWNcdWIyZTRcdWJhNzQgXHVjZDFkIDJcdWJkODRcdWM3NTggXHVjNzkxXHViM2Q5IFx1YzkwMFx1YmU0NCBcdWMyZGNcdWFjMDRcdWM3NzQgXHVkNTQ0XHVjNjk0XHVkNTU4XHVhY2EwXHVhY2UwLCBcdWM3NzQgXHVhY2JkXHVjNmIwXHVhYzAwIFx1Y2Q1Y1x1YzE4Y1x1Yzc3NFx1YmJjMFx1Yjg1YyBcdWIyZjVcdWM3NDAgMlx1YWMwMCBcdWI0MThcdWFjYTBcdWM5YzBcdWM2OTQ/PFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM3NTggXHVhYzFjXHVjMjE4IFRcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWQxXHViMmM4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1YjM3MFx1Yzc3NFx1ZDEzMFx1YjI5NCBcdWI0NTAmbmJzcDtcdWM5MDRcdWM1ZDAgXHVhYzc4XHVjY2QwIFx1YzhmY1x1YzViNFx1YzlkMVx1YjJjOFx1YjJlNC4gXHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWIwOThcdWJiMzQgXHViOWM5XHViMzAwXHVjNzU4IFx1YWMxY1x1YzIxOCBuICgxICZsZTsgbiAmbGU7IDUwMDApIFx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzBcdWFjZTAsIFx1YjJlNFx1Yzc0YyBcdWM5MDRcdWM1ZDAgJm5ic3A7bDxzdWI+MTxcL3N1Yj4sIHc8c3ViPjE8XC9zdWI+LCZuYnNwO2w8c3ViPjI8XC9zdWI+LCB3PHN1Yj4yPFwvc3ViPiwgLi4uICxsPHN1Yj5uPFwvc3ViPiwgdzxzdWI+bjxcL3N1Yj4mbmJzcDsmbmJzcDsoXHVhYzAxIFx1YjljOVx1YjMwMFx1Yzc1OCBcdWFlMzhcdWM3NzRcdWM2NDAgXHViYjM0XHVhYzhjXHViOTdjIFx1YjczYlx1ZDU1OFx1YWNlMCwgMTAwMDBcdWM3NDQgXHViMTE4XHVjOWMwIFx1YzU0YVx1YjI5NCBcdWM4MTVcdWMyMThcdWM3ODVcdWIyYzhcdWIyZTQpIFx1YWMwMCBcdWFjZjVcdWJjMzFcdWM3NDQgXHViNDUwXHVhY2UwIFx1Y2MyOFx1Yjg0MFx1Yjg1YyBcdWM4ZmNcdWM1YjRcdWM5ZDFcdWIyYzhcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWJjYzRcdWI4NWMgXHVkNTQ0XHVjNjk0XHVkNTVjIFx1Y2Q1Y1x1YzE4YyBcdWM3OTFcdWIzZDkgXHVjOTAwXHViZTQ0IFx1YzJkY1x1YWMwNFx1Yzc0NCBcdWQ1NWMgXHVjOTA0XHVjNWQwIFx1YWM3OFx1Y2NkMCBcdWNkOWNcdWI4MjVcdWQ1NjlcdWIyYzhcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiS29yZWFuIn0seyJwcm9ibGVtX2lkIjoiNzM0NCIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6Ildvb2RlbiBTdGlja3MiLCJkZXNjcmlwdGlvbiI6IjxwPlRoZXJlIGlzIGEgcGlsZSBvZiBuIHdvb2RlbiBzdGlja3MuIFRoZSBsZW5ndGggYW5kIHdlaWdodCBvZiBlYWNoIHN0aWNrIGFyZSBrbm93biBpbiBhZHZhbmNlLiBUaGUgc3RpY2tzIGFyZSB0byBiZSBwcm9jZXNzZWQgYnkgYSB3b29kd29ya2luZyBtYWNoaW5lIGluIG9uZSBieSBvbmUgZmFzaGlvbi4gSXQgbmVlZHMgc29tZSB0aW1lLCBjYWxsZWQgc2V0dXAgdGltZSwgZm9yIHRoZSBtYWNoaW5lIHRvIHByZXBhcmUgcHJvY2Vzc2luZyBhIHN0aWNrLiBUaGUgc2V0dXAgdGltZXMgYXJlIGFzc29jaWF0ZWQgd2l0aCBjbGVhbmluZyBvcGVyYXRpb25zIGFuZCBjaGFuZ2luZyB0b29scyBhbmQgc2hhcGVzIGluIHRoZSBtYWNoaW5lLiBUaGUgc2V0dXAgdGltZXMgb2YgdGhlIHdvb2R3b3JraW5nIG1hY2hpbmUgYXJlIGdpdmVuIGFzIGZvbGxvd3M6PFwvcD5cclxuXHJcbjxvbCBzdHlsZT1cImxpc3Qtc3R5bGUtdHlwZTpsb3dlci1hbHBoYVwiPlxyXG5cdDxsaT5UaGUgc2V0dXAgdGltZSBmb3IgdGhlIGZpcnN0IHdvb2RlbiBzdGljayBpcyAxIG1pbnV0ZS48XC9saT5cclxuXHQ8bGk+UmlnaHQgYWZ0ZXIgcHJvY2Vzc2luZyBhIHN0aWNrIG9mIGxlbmd0aCBsIGFuZCB3ZWlnaHQgdyAsIHRoZSBtYWNoaW5lIHdpbGwgbmVlZCBubyBzZXR1cCB0aW1lIGZvciBhIHN0aWNrIG9mIGxlbmd0aCBsJiMzOTsgYW5kIHdlaWdodCB3JiMzOTsgaWYgbCAmbGU7IGwmIzM5OyBhbmQgdyAmbGU7IHcmIzM5Oy4gT3RoZXJ3aXNlLCBpdCB3aWxsIG5lZWQgMSBtaW51dGUgZm9yIHNldHVwLjxcL2xpPlxyXG48XC9vbD5cclxuXHJcbjxwPllvdSBhcmUgdG8gZmluZCB0aGUgbWluaW11bSBzZXR1cCB0aW1lIHRvIHByb2Nlc3MgYSBnaXZlbiBwaWxlIG9mIG4gd29vZGVuIHN0aWNrcy4gRm9yIGV4YW1wbGUsIGlmIHlvdSBoYXZlIGZpdmUgc3RpY2tzIHdob3NlIHBhaXJzIG9mIGxlbmd0aCBhbmQgd2VpZ2h0IGFyZSAoNCw5KSAsICg1LDIpLCAoMiwxKSAsICgzLDUpICwgYW5kICgxLDQpICwgdGhlbiB0aGUgbWluaW11bSBzZXR1cCB0aW1lIHNob3VsZCBiZSAyIG1pbnV0ZXMgc2luY2UgdGhlcmUgaXMgYSBzZXF1ZW5jZSBvZiBwYWlycyAoMSw0KSAsICgzLDUpICwgKDQsOSkgLCAoMiwxKSAsICg1LDIpLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGlucHV0IGNvbnNpc3RzIG9mIFQgdGVzdCBjYXNlcy4gVGhlIG51bWJlciBvZiB0ZXN0IGNhc2VzIChUKSBpcyBnaXZlbiBpbiB0aGUgZmlyc3QgbGluZSBvZiB0aGUgaW5wdXQgZmlsZS4gRWFjaCB0ZXN0IGNhc2UgY29uc2lzdHMgb2YgdHdvIGxpbmVzOiBUaGUgZmlyc3QgbGluZSBoYXMgYW4gaW50ZWdlciBuICwgMSAmbGU7IG4gJmxlOyA1MDAwICwgdGhhdCByZXByZXNlbnRzIHRoZSBudW1iZXIgb2Ygd29vZGVuIHN0aWNrcyBpbiB0aGUgdGVzdCBjYXNlLCBhbmQgdGhlIHNlY29uZCBsaW5lIGNvbnRhaW5zIDJuIHBvc2l0aXZlIGludGVnZXJzIGw8c3ViPjE8XC9zdWI+LCB3PHN1Yj4xPFwvc3ViPiwmbmJzcDtsPHN1Yj4yPFwvc3ViPiwgdzxzdWI+MjxcL3N1Yj4sIC4uLiAsbDxzdWI+bjxcL3N1Yj4sIHc8c3ViPm48XC9zdWI+LCBlYWNoIG9mIG1hZ25pdHVkZSBhdCBtb3N0IDEwMDAwICwgd2hlcmUgbDxzdWI+aTxcL3N1Yj4gYW5kIHc8c3ViPmk8XC9zdWI+IGFyZSB0aGUgbGVuZ3RoIGFuZCB3ZWlnaHQgb2YgdGhlIGkgdGggd29vZGVuIHN0aWNrLCByZXNwZWN0aXZlbHkuIFRoZSAybiBpbnRlZ2VycyBhcmUgZGVsaW1pdGVkIGJ5IG9uZSBvciBtb3JlIHNwYWNlcy48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5UaGUgb3V0cHV0IHNob3VsZCBjb250YWluIHRoZSBtaW5pbXVtIHNldHVwIHRpbWUgaW4gbWludXRlcywgb25lIHBlciBsaW5lLjxcL3A+XHJcblxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJFbmdsaXNoIn1d

출처

ICPC > Regionals > Asia Pacific > Korea > Asia Regional - Taejon 2001 B번

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말

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

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

한국어 | English (Beta)