과제 [백준 - 13904] - python

 

 

def BOJ13904() :
  n = int(input())
  answer = [0] * 10000
  l = []
  for _ in range(n) :
    l.append(list(map(int, input().split())))
  l.sort(key= lambda x : (-x[1]))
  print(l)
  for i in range(n) :
    for j in range(l[i][0] -1, -1, -1) : # 그 날부터 거꾸로 가면서 비어있는칸에 넣어버리자!!
      if answer[j] == 0 : # 마감일보다 전의 날중에 0인 날이 있다면 값을 넣어 주면 됨
        answer[j] = l[i][1]
        break
  print(sum(answer))
BOJ13904()

 

접근방법 :

1. 값을 기준으로 정렬을 시켜준다.

2. 마감일자가 같이 정렬이 되었을텐데. 해당 마감일자부터 거꾸로 접근 하여 비어있는 곳에 넣어준다 (그리디) 아래의 그림으로 설명하겠다.

 

정렬된 값은 [[4, 60], [2, 50], [4, 40], [3, 30], [1, 20], [4, 10], [6, 5]] 이 값이다.

[4,50] -> 4일 부터 마감일을 하나씩 줄여가며 빈칸에 값을 넣는다 4일째가 비어있으므로 4일에 50 투척

[2, 50] -> 2일 부터 마감일을 하나씩 줄여가며 빈칸에 값을 넣는다 2일째가 비어있으므로 2일에 50 투척

[4, 40] -> 4일 부터 마감일을 하나씩 줄여가며 빈칸에 값을 넣는다 3일째가 비어있으므로 3일에 40 투척

[3, 30] -> 3일 부터 마감일을 하나씩 줄여가며 빈칸에 값을 넣는다 1일째가 비어있으므로 1일에 30 투척

[1, 20] -> 1일 부터 마감일을 하나씩 줄여가며 빈칸에 값을 넣는다 빈칸이 없으므로 이 과제는 수행하지 못한다

[4, 10] -> 4일 부터 마감일을 하나씩 줄여가며 빈칸에 값을 넣는다 빈칸이 없으므로 이 과제는 수행하지 못한다

[6, 5] -> 6일 부터 마감일을 하나씩 줄여가며 빈칸에 값을 넣는다 6일째가 비어있으므로 6일에 5투척

 

전부 더하면 우리는 과제를 훌륭히 수행할수 있다!

 

장애물 이였던 것: 

1. 풀이가 계속 생각나지 않아 다른 분들의 풀이방식을 참고하였다

 

 

 

 

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

13904번: 과제

https://blog.naver.com/PostView.naver?blogId=namucoding_pohang&logNo=222367789087&from=search&redirect=Log&widgetTypeCall=true&directAccess=false

[파이썬 알고리즘] Greedy 예제 / BOJ 13904 / 백준 130904