백준 13904 과제 Python3

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

13904번: 과제

최종 코드

• GitHub -> https://github.com/hwayeon351/BEAKJOON-Algorithms/blob/main/BJ13904.py

GitHub - hwayeon351/BEAKJOON-Algorithms: 백준 알고리즘 소스 코드 모음

import sys
def get_max_score(homework, N):
    day = homework[0][0]
    visit = [0]*N
    score = 0
    while day > 0:
        i = -1
        for j in range(N):
            if visit[j]: continue
            if homework[j][0] >= day:
                if i == -1: i = j
                elif homework[j][1] > homework[i][1]: i = j
        if i != -1:
            visit[i] = 1
            score += homework[i][1]
        day -= 1
    print(score)

input = sys.stdin.readline
N = int(input())
homework = list()
for _ in range(N):
    homework.append(list(map(int, input().split())))
homework.sort(reverse = True)
get_max_score(homework, N)

---

풀이 과정

 

import sys
def get_max_score(homework, N):
	#가장 마지막 과제의 남은 일 수로 day 초기화
    day = homework[0][0]
    score = 0
    
    #i번째 과제를 이미 했다면 visit[i] = 1, 아직 안했다면 visit[i] = 0
    visit = [0]*N

    while day > 0:
        i = -1
        
       	#day에 할 수 있는 과제 중 가장 점수가 높은 과제를 선택한다
        for j in range(N):
            if visit[j]: continue
            if homework[j][0] >= day:
                if i == -1: i = j
                elif homework[j][1] > homework[i][1]: i = j
                
        #할 수 있는 과제가 있는 경우,
        if i != -1:
            visit[i] = 1
            score += homework[i][1]
        day -= 1
        
    print(score)

input = sys.stdin.readline
N = int(input())
homework = list()
for _ in range(N):
    homework.append(list(map(int, input().split())))

#과제의 남은 일수와 점수의 역순으로 정렬
homework.sort(reverse = True)
get_max_score(homework, N)

#시간복잡도 = O(n^2), 공간복잡도 = O(n)

---

이전 풀이

풀이 시간 30분

N = int(input())
//dw[i] = [남은 일수, 과제 점수]
dw = [[0,0] for _ in range(N)]
//visit[i] = 0 -> i번째 과제 아직 하지 않음
//visit[i] = 1 -> i번째 과제 함
visit = [0]*N
for i in range(N):
    dw[i] = list(map(int, input().split()))
//남은 일수를 기준으로 내림차순 정렬 -> O(n) = nlogn
dw.sort(reverse = True)
//가장 많이 남은 일수를 timer로 set
timer = dw[0][0]
total = 0
//timer == 0일 때까지 과제 수행 -> O(n) = n^2
while timer > 0:
	//과제 idx
    idx = -1
    for i in range(N):
    	//i번째 과제의 남은 일수가 현재 시간보다 이전이면 해당 과제를 할 수 없다
        if dw[i][0] < timer: break
        //i번째 과제를 할 수 있는 경우
        if visit[i] == 0:
            if idx == -1: idx = i
            //i번째 과제가 현재 시간에서 할 수 있는 과제 중 가장 큰 점수를 가진 경우 idx 값 갱신
            elif dw[idx][1] < dw[i][1]: idx = i
    //할 수 있는 과제가 있는 경우, 과제를 수행한다
    if idx != -1:
        visit[idx] = 1
        total += dw[idx][1]
    timer-=1
print(total)
#시간복잡도 = O(n^2), 공간복잡도 = O(n)