[백준1263번] 시간관리

시간관리
사용언어 : python
Greedy Alogorithm
난이도 : 실버1

✍ 문제

💻 코드

💡초기 알고리즘

L,R=map(int,input().split())
Min=R
if L==R:
    count=0
    l=list(str(L))  
    for i in range(len(l)):
        if l[i]=="8":
            count+=1
else :
    for k in range(L,R):
        count=0
        l=list(str(k))
        for i in range(len(l)):
            if l[i]=="8":
                count+=1
        if count<Min:
            Min=count
        if count==0:
            break
print(Min)

1. 마감시간이 빠른 순서대로 오름차순으로 배열에 정렬
2. 그리고 각각의 Si-Ti한 값은 최대로 늦은 각각의 일처리 시작시간이 됨
3. 배열의 첫번째 값의 Si-Ti가 최대로 늦게 일을 시작할 수 있는 시간이므로 초깃값으로 세팅
   4.초깃값을 기준으로 앞에서 부터 체크한다
4. Ti와 S(i+1)-T(i+1)값을 비교 >이면 뺀 값만큼 초깃값 앞으로 당겨야함 ==이면 그대로 유지 <이면 공백이므로 다른 변수에 누적해서 저장해두며 반복한다
   공백으로 누적해둔 변수는 언제 사용?
   만약 이후에 >의 상황이 발생해서 초깃값을 앞으로 당기기전에 공백누적변수값을 먼저 줄여주는 방식임.

😱 최종 결과 : 실패
실패...한 알고리즘.. 왜?
일단 앞에서 부터 채워넣는다는 발상이 잘못됨.
물론 최대 시작 시간의 값은 맞지만 앞부터 채워넣으면 생각해야할 경우의 수가 너무 많아짐 -> 그래서 위 코드에도 예외상황이 존재해 정답이 아님

즉 맨 뒤부터 꽉꽉 채워나가며 값을 시작시간을 갱신해 나가야함

💡수정된 정답 알고리즘

N=int(input())
TS=[list(map(int,input().split())) for _ in range(N)]
TS.sort(key=lambda x:(x[1],x[0]), reverse=True)

first=TS[0][1]-TS[0][0]
blank=0

print(TS)
for i in range(1,N):
    if TS[i][1]>=first:
        first-=TS[i][0]
    else:
        first=TS[i][1]-TS[i][0]

    if first<0:
        first=-1
        break
                     
print(first)

뒤부터 생각하니 코드가 간결..하고 쉽다..