[백준: Python] 2109 - 순회강연

[문제]

https://www.acmicpc.net/problem/2109

그리디하게 매 순간 가장 큰 강의료를 받을 수 있는지 확인하면 되는 문제입니다.

---

[초기화]

    def __init__(self):
        self.n = int(input())
        self.schedule = [list(map(int, input().split())) for _ in range(self.n)]
        self.visited = [False] * 10001
        self.answer = 0

강의는 특정 일자에 진행하는 것이 아닌, 제안받은 시점으로부터 d일 안에만 가서 강의를 진행하면 됩니다.

 

visited는 이를 위해 어느 시점에 방문했는지 확인하기 위한 용도로 사용될 것입니다.

---

[풀이]

    def solve(self):
        self.schedule.sort(key=lambda x: (-x[0]))  # 수업료가 큰 순으로 정렬
        for pay, day in self.schedule:
            if not self.visited[day]:  # 해당 수업을 진행하기 위해 스케쥴 체크, 해당 스케쥴에 일정이 없다면
                self.visited[day] = True  # 수업 확정
                self.answer += pay
            else:  # 해당 수업을 해당 스케쥴에 못 한다면
                for check in range(day-1, 0, -1):  # d일 안에만 와서 수업하면 되므로 가능한 스케쥴 탐색
                    if not self.visited[check]:  # 빈 스케쥴이 있으면
                        self.visited[check] = True  # 수업 확정
                        self.answer += pay
                        break  # 확정된 시점에서 더 이상 수업을 진행할 필요가 없으므로 탐색 종료
        print(self.answer)

수익을 최대화하기 위해 강의료 순으로 정렬합니다.

 

이후, 현재 일정에 진행할 강의가 없다면 곧바로 진행합니다.

 

만약 그렇지 않다면, d-day 안에 강의를 진행할 수 있는 날이 있는지 확인합니다. 이때 강의를 진행할 수 있다면 진행합니다.

---

[전체 코드]

class Main:
    def __init__(self):
        self.n = int(input())
        self.schedule = [list(map(int, input().split())) for _ in range(self.n)]
        self.visited = [False] * 10001
        self.answer = 0

    def solve(self):
        self.schedule.sort(key=lambda x: (-x[0]))  # 수업료가 큰 순으로 정렬
        for pay, day in self.schedule:
            if not self.visited[day]:  # 해당 수업을 진행하기 위해 스케쥴 체크, 해당 스케쥴에 일정이 없다면
                self.visited[day] = True  # 수업 확정
                self.answer += pay
            else:  # 해당 수업을 해당 스케쥴에 못 한다면
                for check in range(day-1, 0, -1):  # d일 안에만 와서 수업하면 되므로 가능한 스케쥴 탐색
                    if not self.visited[check]:  # 빈 스케쥴이 있으면
                        self.visited[check] = True  # 수업 확정
                        self.answer += pay
                        break  # 확정된 시점에서 더 이상 수업을 진행할 필요가 없으므로 탐색 종료
        print(self.answer)

---