순회강연 ⭐

❌ 잘못된 접근 (함정)

1. 강연료를 기준으로 내림차순 정렬
2. 마감일이 같은 것들 중 가장 비싼 것만 선택
3. 문제점: lectures = [[10, 1], [100, 2], [150, 2]]의 경우
   • 잘못된 로직: 1일차에 10, 2일차에 150 선택 → 160
   • 올바른 답: 1일차에 100, 2일차에 150 선택 → 250

⭕ 방법 1 (boolean 배열 방식)

1. 마감일이 겹치면 강연료가 제일 큰 것을 택해야 하지만, 이후 더 큰 마감일을 가진 것 중에 버려지는 것이 있다면 그것을 대신 택해야 한다.

2. 마감일이 낮은 순서로 처리하면 미래에 일어나는 일을 계산하는 것이 쉽지 않다.

3. 결국 무엇을 포기해야 하는 것이므로 비싼 것을 위주로 선택해야 한다.

4. 강연료를 기준으로 내림차순 정렬을 한다.

5. boolean[]로 해당 날짜에 주인이 있는지 여부를 선택한다. 주인 있다면 정렬이 되었으므로, 무조건 주인의 강연료 이상일 수 밖에 없다. boolean[]의 크기는 최대 마감일로 설정한다. 그 이상은 될 수 없다.

6. 즉, 해당 날짜에 주인이 있다면 그 날짜는 넘어가야 한다.

7. 비싼 강연이라도 최대한 마감일에 가깝게 처리해야 더 돈을 많이 받을 수 있다.

   즉, 마감일부터 줄여가며 반복을 돌아야 한다.

💡 추가 설명

• 이 방법의 핵심은 "가능한 가장 늦은 날짜에 배치"하는 그리디 전략이다. 비싼 강연을 마감일에 가깝게 배치함으로써 다른 강연들이 들어갈 수 있는 기회를 최대한 보장한다.

  // 예시: [100, 3] 강연의 경우
  for (int j = 3; j > 0; j--) { // 3일 → 2일 → 1일 순으로 확인
      if (!isScheduled[j - 1]) {
          isScheduled[j - 1] = true; // 가능한 가장 늦은 날짜에 배치
          break;
      }
  }
  

⭕ 방법 2 (우선순위 큐 방식)

1. 내부 해부 과정에서 문제는 마감일이 낮은 순서로 정렬 후 가장 높은 강연을 택하면 이후에 버려지는 기회 중 더 좋은 기회를 놓치게 된다.

2. 그렇다면, 마감일이 낮은 순서로 정렬 후 높은 강연을 택하는 것은 유지하고, 이것을 확정하지 않고 추후 더 좋은 것이 나오면 기존의 것을 버리면 된다.

3. 이전의 풀었던 명예의 전당처럼 베스트 멤버를 유지하는 것처럼, 마감일이 낮은 순서로 정렬된 배열에서 하나씩 꺼내서 강연료 오름차순 우선순위 큐에 넣는다.

4. 베스트 멤버의 길이는 해당 날짜이다. 길이가 4일이면 4일차로, 더 좋은 경우의 수를 유지할 수 있다.

💡 추가 설명

• 이 방법은 "동적 최적화"이다. 마감일을 하나의 체크포인트로 생각하면, 각 체크포인트에서 "지금까지 선택할 수 있는 최고의 조합"을 계속 업데이트하는 것.

  // 핵심 로직
  if (lectures[i][1] < pq.size()) {
      pq.poll(); // 현재까지 선택된 것 중 가장 작은 것을 제거
  }
  

💡 왜 이 조건이 중요한가?

• 마감일이 3이면 최대 3개의 강연만 할 수 있음
• 큐 크기가 3을 초과하면 불가능한 상황이므로 가장 작은 것을 버림

⭕ 실제 데이터 흐름 (방법 2)

• 7개의 데이터가 들어온다.
• lectures = [[20, 1], [2, 1], [10, 3], [100, 2], [8, 2], [5, 20], [50, 10]]로 데이터가 들어온다.
• 마감일을 기준으로 오름차순 정렬한다.
• lectures = [[20, 1], [2, 1], [100, 2], [8, 2], [10, 3], [50, 10], [5, 20]]
• 각 강연을 순차적으로 처리
  • [20, 1]: 큐에 20 추가, 큐 크기(1) ≤ 마감일(1) → 유지
  • [2, 1]: 큐에 2 추가, 큐 크기(2) > 마감일(1) → 최솟값 2 제거
  • [100, 2]: 큐에 100 추가, 큐 크기(2) ≤ 마감일(2) → 유지
  • [8, 2]: 큐에 8 추가, 큐 크기(3) > 마감일(2) → 최솟값 8 제거
  • [10, 3]: 큐에 10 추가, 큐 크기(3) ≤ 마감일(3) → 유지
  • [50, 10]: 큐에 50 추가, 큐 크기(4) ≤ 마감일(10) → 유지
  • [5, 20]: 큐에 5 추가, 큐 크기(5) ≤ 마감일(20) → 유지
• 최종 큐 : [10, 20, 50, 100, 5]
• 합계 : 10 + 20 + 50 + 100 + 5 = 185

💡 추가 인사이트

• 이 과정에서 주목할 점은 [2, 1]과 [8, 2]가 제거되었다. 이들은 각각의 마감일 시점에서 "최선이 아닌 선택"이었기 때문이다.
• 이처럼 우선순위 큐는 **"지금까지의 최선"**을 계속 갱신하면서 최적해를 찾아간다.

💡 두 방법의 시간복잡도 비교

• 방법 1 (boolean 배열) : O(N × D) - D는 최대 마감일
• 방법 2 (우선순위 큐) : O(N log N) - 일반적으로 더 효율적