🙄 백준 11497 : 통나무 건너뛰기

13904: 과제

Greedy 문제이다.

이번 문제는 쉽다고 생각했는데,, 계속 오류가 나서 다른 분 블로그를 참고했다.

📌 Try 1

# input
n = int(input())
inputArr = list()
for _ in range(n):
  inputArr.append(list(map(int, input().split())))

# sorting
inputArr.sort(key=lambda x:(x[1], x[0]), reverse=True)

maxIdx, cnt, SUM = 0, 1, 0
for i in range(n):
  if maxIdx < inputArr[i][0]:
    maxIdx = inputArr[i][0]
  if cnt <= maxIdx:
    SUM += inputArr[i][1]
    cnt += 1

print(SUM)

접근 방법은 다음과 같이 했습니다.

1) score를 기준으로 내림차순 정렬하고, deadline을 기준으로 다시 내림차순을 정렬한다.

2) 각 요소를 순서대로 탐색하며, 가장 긴 dealine을 계속 기록한다.

3) 가장 긴 deadline만큼 list를 탐색해서 sum에 더한다.

입출력 예시는 잘 나왔지만,,, 틀렸습니다가 떴습니다.

예외를 찾을 수가 없어서 다른 분 블로그를 참고해서 풀었습니다.

이 방법이 왜 틀렸는지 아직도 모르겠습니다😥

📌 Try 2

# input
n = int(input())
inputArr = list()
for _ in range(n):
  inputArr.append(list(map(int, input().split())))

# sorting
inputArr.sort(key=lambda x:(x[1], x[0]), reverse=True)
visit = [0] * (1001)

for x in inputArr:
  idx = x[0]
  while idx > 0:
    if visit[idx] == 0:
      visit[idx] = x[1]
      break
    idx -= 1
    
print(sum(visit))

1) 문제별로 과제 점수가 높은순으로 정렬한다.

2) 과제 점수가 높은순으로 정렬되었으면, 마감일이 많이 남은건 가장 늦게 끝내야한다.

따라서, 과제 점수가 높은순으로 마감일에 최대한 가깝게 탐욕적으로 넣어준다.

조건 : d (1 ≤ d ≤ 1,000) 이므로 visit list의 length를 1001으로 설정해줬다.

🎁 Reference

• [백준] 13904번: 과제(그리디)
  https://zzang9ha.tistory.com/207