백준 온라인 저지, 그리디 / 7983번: 내일할거야 (파이썬 / 백준 골드문제)

문제

아 과제 하기 싫다. 아무 것도 안 하고 싶다. 더 적극적이고 격렬하게 아무 것도 안 하고 싶다.

있잖아. 내가 아까 책상에다가 n개의 과제 목록을 적어놨어. 각각의 과제 i는 d_i 일이 걸리고, 오늘로부터 t_i 일 안에 끝내야 해. 그러니까 오늘이 0일이면, t_i일이 끝나기 전에 제출이야. 과제는 한번 시작하면 쉬지 않고 계속해야 해. 안 그러면 머리 아파 지거든.

근데 있잖아. 내가 지금 너무, 너무 아무 것도 안 하고 싶어. 그래서 오늘은 아무 것도 안 할 거야. 더 중요한 게 뭔지 알아? 사실 나 내일도, 모레도, 아무 것도 안 하고 싶어. 한 며칠 동안은 계속 아무 것도 안하려고. 아. 과제가 있을 때 내가 내일부터 연속으로 최대 며칠동안 놀 수 있는지 궁금하다. 궁금하긴 한데, 난 아무 것도 안 하고 싶어.

좋은 생각이 났다. 너희가 이걸 대신 구해주면, 내가 너희의 맞은 문제 수를 하나 올려줄게.

입력

첫째 줄에는 과제의 개수인 정수 n (1 ≤ n ≤ 10⁶)이 주어진다.

이후 n개의 줄에 각각의 과제를 나타내는 두 정수 d_i, t_i (1 ≤ d_i, t_i ≤ 10⁹)가 순서대로 주어진다. 오늘은 0일이다.

모든 입력에 대해, 오늘 아무 것도 안 해도 과제를 마무리 할 수 있는 방법이 존재함이 보장된다.

출력

내일(1일)부터 연속으로 최대 며칠 동안 놀 수 있는지를 출력한다. 가령, 답이 0이면, 내일 과제를 해야 하며, 1 이면, 모레에 과제를 해야 한다.

제한

예제 입력 1

3
2 8
1 13
3 10

예제 출력 1

5

힌트

1–5일에는 놀고, 6–7일에는 1번째 과제를, 8–10일에는 3번째 과제를 한다. 11–12일에는 놀고, 13–13 일에 2번째 과제를 한다.

W3sicHJvYmxlbV9pZCI6Ijc5ODMiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWIwYjRcdWM3N2MgXHVkNTYwXHVhYzcwXHVjNTdjIiwiZGVzY3JpcHRpb24iOiI8cD5cdWM1NDQgXHVhY2ZjXHVjODFjIFx1ZDU1OFx1YWUzMCBcdWMyZWJcdWIyZTQuIFx1YzU0NFx1YmIzNCBcdWFjODNcdWIzYzQgXHVjNTQ4IFx1ZDU1OFx1YWNlMCBcdWMyZjZcdWIyZTQuIFx1YjM1NCBcdWM4MDFcdWFkZjlcdWM4MDFcdWM3NzRcdWFjZTAgXHVhY2E5XHViODJjXHVkNTU4XHVhYzhjIFx1YzU0NFx1YmIzNCBcdWFjODNcdWIzYzQgXHVjNTQ4IFx1ZDU1OFx1YWNlMCBcdWMyZjZcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1Yzc4OFx1Yzc5Nlx1YzU0NC4gXHViMGI0XHVhYzAwIFx1YzU0NFx1YWU0YyBcdWNjNDVcdWMwYzFcdWM1ZDBcdWIyZTRcdWFjMDAgblx1YWMxY1x1Yzc1OCBcdWFjZmNcdWM4MWMgXHViYWE5XHViODVkXHVjNzQ0IFx1YzgwMVx1YzViNFx1YjFhOFx1YzViNC4gXHVhYzAxXHVhYzAxXHVjNzU4IFx1YWNmY1x1YzgxYyBpXHViMjk0IGQ8c3ViPmk8XC9zdWI+IFx1Yzc3Y1x1Yzc3NCBcdWFjNzhcdWI5YWNcdWFjZTAsIFx1YzYyNFx1YjI5OFx1Yjg1Y1x1YmQ4MFx1ZDEzMCB0PHN1Yj5pPFwvc3ViPiBcdWM3N2MgXHVjNTQ4XHVjNWQwIFx1YjA1ZFx1YjBiNFx1YzU3YyBcdWQ1NzQuIFx1YWRmOFx1YjdlY1x1YjJjOFx1YWU0YyBcdWM2MjRcdWIyOThcdWM3NzQgMFx1Yzc3Y1x1Yzc3NFx1YmE3NCwgdDxzdWI+aTxcL3N1Yj5cdWM3N2NcdWM3NzQgXHViMDVkXHViMDk4XHVhZTMwIFx1YzgwNFx1YzVkMCBcdWM4MWNcdWNkOWNcdWM3NzRcdWM1N2MuIFx1YWNmY1x1YzgxY1x1YjI5NCBcdWQ1NWNcdWJjODggXHVjMmRjXHVjNzkxXHVkNTU4XHViYTc0IFx1YzI2Y1x1YzljMCBcdWM1NGFcdWFjZTAgXHVhY2M0XHVjMThkXHVkNTc0XHVjNTdjIFx1ZDU3NC4gXHVjNTQ4IFx1YWRmOFx1YjdlY1x1YmE3NCBcdWJhMzhcdWI5YWMgXHVjNTQ0XHVkMzBjIFx1YzljMFx1YWM3MFx1YjRlMC48XC9wPlxyXG5cclxuPHA+XHVhZGZjXHViMzcwIFx1Yzc4OFx1Yzc5Nlx1YzU0NC4gXHViMGI0XHVhYzAwIFx1YzljMFx1YWUwOCBcdWIxMDhcdWJiMzQsIFx1YjEwOFx1YmIzNCBcdWM1NDRcdWJiMzQgXHVhYzgzXHViM2M0IFx1YzU0OCBcdWQ1NThcdWFjZTAgXHVjMmY2XHVjNWI0LiBcdWFkZjhcdWI3OThcdWMxMWMgXHVjNjI0XHViMjk4XHVjNzQwIFx1YzU0NFx1YmIzNCBcdWFjODNcdWIzYzQgXHVjNTQ4IFx1ZDU2MCBcdWFjNzBcdWM1N2MuIFx1YjM1NCBcdWM5MTFcdWM2OTRcdWQ1NWMgXHVhYzhjIFx1YmI1NFx1YzljMCBcdWM1NGNcdWM1NDQ/IFx1YzBhY1x1YzJlNCBcdWIwOTggXHViMGI0XHVjNzdjXHViM2M0LCBcdWJhYThcdWI4MDhcdWIzYzQsIFx1YzU0NFx1YmIzNCBcdWFjODNcdWIzYzQgXHVjNTQ4IFx1ZDU1OFx1YWNlMCBcdWMyZjZcdWM1YjQuIFx1ZDU1YyBcdWJhNzBcdWNlNjAgXHViM2Q5XHVjNTQ4XHVjNzQwIFx1YWNjNFx1YzE4ZCBcdWM1NDRcdWJiMzQgXHVhYzgzXHViM2M0IFx1YzU0OFx1ZDU1OFx1YjgyNFx1YWNlMC4gXHVjNTQ0LiBcdWFjZmNcdWM4MWNcdWFjMDAgXHVjNzg4XHVjNzQ0IFx1YjU0YyBcdWIwYjRcdWFjMDAgXHViMGI0XHVjNzdjXHViZDgwXHVkMTMwIFx1YzVmMFx1YzE4ZFx1YzczY1x1Yjg1YyBcdWNkNWNcdWIzMDAgXHViYTcwXHVjZTYwXHViM2Q5XHVjNTQ4IFx1YjE4MCBcdWMyMTggXHVjNzg4XHViMjk0XHVjOWMwIFx1YWQ4MVx1YWUwOFx1ZDU1OFx1YjJlNC4gXHVhZDgxXHVhZTA4XHVkNTU4XHVhZTM0IFx1ZDU1Y1x1YjM3MCwgXHViMDljIFx1YzU0NFx1YmIzNCBcdWFjODNcdWIzYzQgXHVjNTQ4IFx1ZDU1OFx1YWNlMCBcdWMyZjZcdWM1YjQuPFwvcD5cclxuXHJcbjxwPlx1Yzg4Ylx1Yzc0MCBcdWMwZGRcdWFjMDFcdWM3NzQgXHViMGFjXHViMmU0LiBcdWIxMDhcdWQ3NmNcdWFjMDAgXHVjNzc0XHVhYzc4IFx1YjMwMFx1YzJlMCBcdWFkNmNcdWQ1NzRcdWM4ZmNcdWJhNzQsIFx1YjBiNFx1YWMwMCBcdWIxMDhcdWQ3NmNcdWM3NTggXHViOWRlXHVjNzQwIFx1YmIzOFx1YzgxYyBcdWMyMThcdWI5N2MgXHVkNTU4XHViMDk4IFx1YzYyY1x1YjgyNFx1YzkwNFx1YWM4Yy48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVhY2ZjXHVjODFjXHVjNzU4IFx1YWMxY1x1YzIxOFx1Yzc3OCBcdWM4MTVcdWMyMTggbiAoMSAmbGU7IG4gJmxlOyAxMDxzdXA+NjxcL3N1cD4pXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjNzc0XHVkNmM0IG5cdWFjMWNcdWM3NTggXHVjOTA0XHVjNWQwIFx1YWMwMVx1YWMwMVx1Yzc1OCBcdWFjZmNcdWM4MWNcdWI5N2MgXHViMDk4XHVkMGMwXHViMGI0XHViMjk0IFx1YjQ1MCBcdWM4MTVcdWMyMTggZDxzdWI+aTxcL3N1Yj4sIHQ8c3ViPmk8XC9zdWI+ICgxICZsZTsgZDxzdWI+aTxcL3N1Yj4sIHQ8c3ViPmk8XC9zdWI+ICZsZTsgMTA8c3VwPjk8XC9zdXA+KVx1YWMwMCBcdWMyMWNcdWMxMWNcdWIzMDBcdWI4NWMgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWM2MjRcdWIyOThcdWM3NDAgMFx1Yzc3Y1x1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViYWE4XHViNGUwIFx1Yzc4NVx1YjgyNVx1YzVkMCBcdWIzMDBcdWQ1NzQsIFx1YzYyNFx1YjI5OCBcdWM1NDRcdWJiMzQgXHVhYzgzXHViM2M0IFx1YzU0OCBcdWQ1NzRcdWIzYzQgXHVhY2ZjXHVjODFjXHViOTdjIFx1YjljOFx1YmIzNFx1YjlhYyBcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWJjMjlcdWJjOTVcdWM3NzQgXHVjODc0XHVjN2FjXHVkNTY4XHVjNzc0IFx1YmNmNFx1YzdhNVx1YjQxY1x1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWIwYjRcdWM3N2MoMVx1Yzc3YylcdWJkODBcdWQxMzAgXHVjNWYwXHVjMThkXHVjNzNjXHViODVjIFx1Y2Q1Y1x1YjMwMCBcdWJhNzBcdWNlNjAgXHViM2Q5XHVjNTQ4IFx1YjE4MCBcdWMyMTggXHVjNzg4XHViMjk0XHVjOWMwXHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC4gXHVhYzAwXHViODM5LCBcdWIyZjVcdWM3NzQgMFx1Yzc3NFx1YmE3NCwgXHViMGI0XHVjNzdjIFx1YWNmY1x1YzgxY1x1Yjk3YyBcdWQ1NzRcdWM1N2MgXHVkNTU4XHViYTcwLCAxIFx1Yzc3NFx1YmE3NCwgXHViYWE4XHViODA4XHVjNWQwIFx1YWNmY1x1YzgxY1x1Yjk3YyBcdWQ1NzRcdWM1N2MgXHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiI8cD4xJm5kYXNoOzVcdWM3N2NcdWM1ZDBcdWIyOTQgXHViMTgwXHVhY2UwLCA2Jm5kYXNoOzdcdWM3N2NcdWM1ZDBcdWIyOTQgMVx1YmM4OFx1YzlmOCBcdWFjZmNcdWM4MWNcdWI5N2MsIDgmbmRhc2g7MTBcdWM3N2NcdWM1ZDBcdWIyOTQgM1x1YmM4OFx1YzlmOCBcdWFjZmNcdWM4MWNcdWI5N2MgXHVkNTVjXHViMmU0LiAxMSZuZGFzaDsxMlx1Yzc3Y1x1YzVkMFx1YjI5NCBcdWIxODBcdWFjZTAsIDEzJm5kYXNoOzEzIFx1Yzc3Y1x1YzVkMCAyXHViYzg4XHVjOWY4IFx1YWNmY1x1YzgxY1x1Yjk3YyBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwib3JpZ2luYWwiOiIwIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJLb3JlYW4ifSx7InByb2JsZW1faWQiOiI3OTgzIiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiRG8gSXQgVG9tb3Jyb3ciLCJkZXNjcmlwdGlvbiI6IjxwPkJ5dGVhc2FyIHRlbmRzIHRvIHBvc3Rwb25lIGFsbCB0aGUgdGFza3MgaGUgbmVlZHMgdG8gcGVyZm9ybS4gSG93ZXZlciwgaWYgaGUgcHJvbWlzZXMgdG8gZG8gc29tZXRoaW5nLCB5b3UgY2FuIGNlcnRhaW5seSBjb3VudCBvbiBoaW0uPFwvcD5cclxuXHJcbjxwPkJ5dGVhc2FyIHdva2UgdXAgZWFybHkgdG9kYXkgYW5kIHByZXBhcmVkIGEgbGlzdCBvZiBuIHRhc2tzIHRoYXQgaGUgbmVlZHMgdG8gcGVyZm9ybSBpbiBuZWFyIGZ1dHVyZS4gVGhlIGktdGggdGFzayB3aWxsIHRha2UgaGltIGQ8c3ViPmk8XC9zdWI+IGNvbnNlY3V0aXZlIGRheXMgdG8gcGVyZm9ybSBhbmQgaGFzIHRvIGJlIGNvbXBsZXRlZCB3aXRoaW4gdGhlIG5leHQgdDxzdWI+aTxcL3N1Yj4gZGF5cywgc3RhcnRpbmcgZnJvbSB0b2RheS4gQnl0ZWFzYXIgd291bGQgbGlrZSB0byBrbm93IGhvdyBtdWNoIHRpbWUgaGUgY2FuIHNwZW5kIGRvaW5nIG5vdGhpbmcgdW50aWwgaGUgcmVhbGx5IGhhcyB0byBzdGFydCBwZXJmb3JtaW5nIHNvbWUgdGFza3MuIENvdWxkIHlvdSB3cml0ZSBhIHByb2dyYW0gdGhhdCB3aWxsIGhlbHAgaGltIGZpbmQgdGhhdCBvdXQ/IEJ5dGVhc2FyIGNvdWxkIGFsc28gd3JpdGUgc3VjaCBhIHByb2dyYW0gaGltc2VsZiwgaG93ZXZlciB0aGlzIGNvdWxkIGRpc3R1cmIgaGlzIHByb2NyYXN0aW5hdGlvbiBwZXJpb2QuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgZmlyc3QgbGluZSBvZiBpbnB1dCBjb250YWlucyBvbmUgaW50ZWdlciBuICgxICZsZTsgbiAmbGU7IDEgMDAwIDAwMCk6IHRoZSBudW1iZXIgb2YgdGFza3MgdGhhdCBCeXRlYXNhciBoYXMgdG8gcGVyZm9ybS4gVGhlIGZvbGxvd2luZyBuIGxpbmVzIGhvbGQgYSBkZXNjcmlwdGlvbiBvZiB0aGUgdGFza3MuIFRoZSBpLXRoIG9mIHRob3NlIGxpbmVzIGNvbnRhaW5zIHR3byBpbnRlZ2VycyBkPHN1Yj5pPFwvc3ViPiBhbmQgdDxzdWI+aTxcL3N1Yj4gKDEgJmxlOyBkPHN1Yj5pPFwvc3ViPiwgdDxzdWI+aTxcL3N1Yj4gJmxlOyAxMDxzdXA+OTxcL3N1cD4pLiBXZSBhc3N1bWUgdGhhdCBCeXRlYXNhciBpcyBhYmxlIHRvIHBlcmZvcm0gYWxsIHRoZSB0YXNrcyBvbiB0aW1lLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPllvdXIgcHJvZ3JhbSBzaG91bGQgb3V0cHV0IG9uZSBpbnRlZ2VyIGs6IHRoZSBtYXhpbXVtIG51bWJlciBvZiBkYXlzIGR1cmluZyB3aGljaCBCeXRlYXNhciBjYW4gYXZvaWQgd29ya2luZy4gSW4gb3RoZXIgd29yZHMsIG9uIHRoZSBkYXkgbnVtYmVyIGsgKyAxIGF0IGxhdGVzdCBCeXRlYXNhciBtdXN0IHN0YXJ0IHBlcmZvcm1pbmcgb25lIG9mIHRoZSB0YXNrcyBpbiBvcmRlciB0byBiZSBhYmxlIHRvIGV2ZW50dWFsbHkgY29tcGxldGUgYWxsIHRoZSB0YXNrcyBvbiB0aW1lLjxcL3A+XHJcbiIsImhpbnQiOiI8cD5Gb3IgdGhlIGZpcnN0IDUgZGF5cyBCeXRlYXNhciByZXN0cy4gT24gdGhlIGZvbGxvd2luZyA1IGRheXMgaGUgcGVyZm9ybXMgdGhlIGZpcnN0IGFuZCB0aGUgdGhpcmQgdGFzayAoaW4gdGhhdCBvcmRlcikuIEFmdGVyd2FyZHMgaGUgcmVzdHMgZm9yIDEgZGF5IGFuZCBwZXJmb3JtcyB0aGUgc2Vjb25kIHRhc2ssIHdoaWNoIHRha2VzIGhpbSAyIGRheXMuPFwvcD5cclxuIiwib3JpZ2luYWwiOiIxIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJFbmdsaXNoIn1d

접근 방법

- 0. 주어진 과제를 마무리해야하는 시간을 기준으로 내림차순으로 정렬한다.
- 1. 과제를 하나씩 탐색하며 과제를 마무리할 수 있는 시간을 다음과 같이 설정한다.
- min(현재 탐색 중인 과제의 t, 현재까지 저장된 여유시간) - 현재 탐색 중인 과제의 d
- 2. 모든 탐색이 끝난 뒤, 과제를 마무리할 수 있는 최대한 늦은 시간을 출력한다.

코드

# https://www.acmicpc.net/problem/7983
# 접근방법
# 0. 주어진 과제를 마무리해야하는 시간을 기준으로 내림차순으로 정렬한다.
# 1. 과제를 하나씩 탐색하며 과제를 마무리할 수 있는 시간을 다음과 같이 설정한다.
# min(현재 탐색 중인 과제의 t, 현재까지 저장된 여유시간) - 현재 탐색 중인 과제의 d
# 2. 모든 탐색이 끝난 뒤, 과제를 마무리할 수 있는 최대한 늦은 시간을 출력한다.
import sys
input = sys.stdin.readline
n = int(input())
work = [list(map(int, input().split())) for _ in range(n)]
work.sort(key=lambda x: x[1], reverse = True)
spare_time = work[0][1]
for i in range(n):
    spare_time = min(work[i][1], spare_time) - work[i][0]
print(spare_time)