[문제]
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)
'Algorithm > 백준' 카테고리의 다른 글
| [백준: Python] 2458 - 키 순서 (0) | 2024.12.05 |
|---|---|
| [백준: Java] 7490 - 0 만들기 (0) | 2024.11.26 |
| [플랫폼: Python] 16954 - 움직이는 미로 탈출 (0) | 2024.11.24 |
| [백준: Python] 18428 - 감시 피하기 (0) | 2024.11.23 |
| [백준: Python] 18427 - 함께 블록 쌓기 (0) | 2024.11.22 |