13904과제-python

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

13904번: 과제

1. 문제풀이

문제는 간단하다. 각 줄마다 마감일 + 점수가 주어지는데 하루에 한가지 점수만 얻을 수 있다. 이 중 어떻게 해야 최대 점수를 받을수 있을지를 구하는 문제였다. 크게 두가지로 생각을 하였다.

지금 닥친 것 중에 제일 큰 것들을 해결해주자 vs 제일큰 점수들위주로 sort를 하고 그것들을 위주로 실행을 가능하게 하자.

생각을 해보니 두번째 방법이 문제해결에 맞는 방법이여서 두번째 방법으로 진행을 하였다. 

그런데 다시 막힌게 그러면 첫날부터 제일 큰 점수들위주로 한다고 가정하면 마감일이 다양한 경우 내가 못하고 넘어가는 경우가 있을테니 거꾸로 돌려서 마지막날 부터 제일 급한것들을 해주자! 결국 저 vs두개를 섞은 방법을 생각해냈다.

7
4 60
4 40
1 20
2 50
3 30
4 10
6 5

예를 들어 input이 이렇게 들어가면 마지막날 6일차에는 5의 업무를 하고 5에는 없으니 못하구 4에는 60이라는 업무를 하고 3일차에는 40,30,10중 가장큰 40의 업무를 하고 2일차에는 50,30,10,중 50을 하고 1일차에는 20, 30,10 중 30을 하게 된다! 이렇게 생각하니 문제가 간단해졌다.

시간복잡도는 N제곱으로 해결하면 될거라 생각해서 큰 지장은 없었다ㅏ.

work = [0 for _ in range(1000)]

차피 최대 1000일이니 이렇게 배열을 만들어주고

import sys
input = sys.stdin.readline
N = int(input())
tasklist = [tuple(map(int,input().split())) for _ in range(N)]
tasklist.sort(reverse=True, key= lambda x : x[1])
work = [0 for _ in range(1000)]
for i in range(N):
    for j in range(tasklist[i][0]-1, -1, -1):
        if work[j] == 0:
            work[j] = tasklist[i][1]
            break
print(sum(work))

먼저 tasklist가 일 순으로 정렬이 되고 난후 일이 큰순으로 먼저 해당하는 일에 넣어준다.

그리고 work가 0으로 준 이유가 스케쥴이 없다는 것을 뜻하는 건데 만약 그 날 일을 한다면 하나씩 땡기면서 일을 시켜주면 된다. 

아래는 내가 글로쓰며 푼 풀이방식이다.! 악필이라인식이 어려우면 댓글로 남겨주세요