20126번: 교수님의 기말고사 (구현)

20126번: 교수님의 기말고사

• 일반적인 경우에 i번째 시험과 i+1번째 시험 사이에 끼어들려면 x(i+1) - (x(i)+y(i)) >= M 이어야 한다. 이때 i를 0부터 n-2까지 해야 0번째부터 시작해서 n-1번째 시험 사이로 끼어들 수 있다(문제에서는 1부터 카운팅하나 나는 0부터 세는게 편해서 이렇게 표현)
• 위 일반적인 경우를 제외하고는 가능한 경우가 0번째 시험이 시작하기 전에 시험을 진행하는 경우와 n-1번째(마지막) 시험이 끝난 후에 x(n-1)+y(n-1) + M <= S 면 시험을 칠 수 있다. 
• 위 경우들이 안된다면 시험을 볼 수 없는 것이다.

위와 같이 3가지를 문제를 풀기에 생각을 했고, 각 경우들의 우선순위를 잘 생각해서 if 문을 구성하면 되는 문제이다. 

우선순위는 가능한 빨리 시험을 보는 경우이므로, if 문을 짤 때 우선순위는 다음과 같다. 

1. 0번째 시험이 시작하기 전에 시험을 진행하는 경우
2. 0~n-1번째 시험 사이에 껴서 시험을 보는 경우
3. 마지막 시험이 끝난 이후 시험을 보는 경우
4. 1,2,3 만족 안하는 경우

이렇게 짜서 제출해보니 틀렸다고 나와서 알고리즘에는 문제가 없었는데 입력데이터에 시간 순서대로 입력되지 않은 경우가 있을 수도 있는 것 같아서 x에 따라 오름차순으로 정렬한 후 제출해보니 맞았다.

n,m,s = map(int,input().split())
arr = []
for i in range(n):
    x,y = map(int,input().split())
    arr.append((x,y))
arr.sort()
def solve():
    for i in range(0,n-1):
        if arr[i + 1][0] - arr[i][0] - arr[i][1] >= m:
            return (arr[i][0] + arr[i][1])
def solve2():
    if arr[-1][0] + arr[-1][1] + m <= s:
        return arr[-1][0] + arr[-1][1]
if arr[0][0] >= m:
    print(0)
elif solve() != None:
    print(solve())
elif solve2() != None:
    print(solve2())
else:
    print(-1)