Python으로 푸는 백준 2109. 순회강연

백준 2109. 순회강연

저명한 학자에게 여러 대학에서 강연 요청이 들어 왔다.

각 대학에서는 몇일 안에 와서 강연을 해주면 얼마의 강연비를 주겠다고 제시했다.

학자가 하루에 한 곳에서만 강연을 할 수 있으므로,

최대한 유리하게 스케줄을 짜서, 가장 많은 돈을 벌 수 있도록 순회 강연을 하려고 한다.

이 학자가 최대 벌 수 있는 강연비는 총 얼마인가?

문제 보러 가기

github에서 코드 보기

문제에서 제시한 조건

- n개의 대학에서 d일 안에 와서 강연을 해주면 p만큼의 강연료를 지불하겠다고 알려준다.

- 4개의 대학에서 제시한 p값이 각각 50, 10, 20, 30이고, d 값이 차례로 2, 1, 2, 1이라고 하자. 이럴 대에서는 첫째 날에 4번 대학에서 강연을 하고, 둘째 날에 1번 대학에서 강연을 하면 80만큼의 돈을 벌 수 있다.

코드 리뷰

총 두가지 방식으로 문제를 풀었다. 시도는 방식2를 먼저 해보았으나 시간 초과로 실패하였다.

방식1로 문제를 푸는데는 성공했으나 시간을 꽤 많이 소비했다. 엄청 짧은 코드로 짧은 시간에 푼 사람도 있었다.

실패한 코드는 나중에 다시 보고 리뷰하고자 올려두었다.

방식1. 제시된 기한별로 몇개의 선택지가 있는지 알아내고 (d가 1000인 옵션이 100개이고, 그 다음 d가 1이라면, d가 1000인 옵션은 모두 수용이 가능하다.) 수용가능한 경우 다 더해주고 아닌 경우에만 정렬해 계산하는 방법. 기한 옵션의 수만큼 while문을 돌린다.

방식2. 남은 선택지의 기한을 1만큼 줄여나가 더이상 선택 가능한 옵션이 없을 떄까지 계산, 선택지의 수만큼 while문을 돌린다.

문제 풀이 방법 

제시된 기한별로 몇개의 옵션이 있는지, 몇개의 기한이 있는지 집합에 넣어서 알아낸 후 정렬된 옵션리스트에서 선택가능한 옵션들이 어느 index까지인지 계산하여 fee를 더해주고 그렇지 않은 경우에는 기한을 변경하여 다시 계산하여 문제를 해결한다.

다음과 같은 경우를 풀때 최적의 알고리즘을 고려한 것이다. 

100000

10 100000

10 100000

10 100000

...

10 100000

수도 코드

sort optionList by p # 강연비를 기준으로 정렬

sort optionList by d in descending order # 기한을 기준으로 정렬

total = 0

while dSet:

# 강연을 갈 수 있는 횟수(first_d - next_d)와 해당 기한의 강연 수를 비교하여 계산한다.

if  first_d - next_d >= dCount:

# 기한 내 강연 fee 합산

total += option_fee

else:

# dcount만큼 fee 기준으로 selected_options 정렬

if 기한 내: 강연 fee 합산

elif 기간 초과: 강연은 다음 기한 값으로 변경

return total

파이썬 코드

import sys
 
def greedy(feeList, dCountList, dSet):
    total = 0
    feeList = sorted(feeList, key=lambda fee:fee[0], reverse=True)
    feeList = sorted(feeList, key=lambda fee: fee[1], reverse=True)
 
    while dSet:
        first_d = dSet.pop(0) # 첫번째 기한 값
        next_d = 0 # 기한 옵션이 하나라면 0 이어야 1일을 포함하여 가능 횟수를 셀 수 있음
        if len(dSet) > 0:
            next_d = dSet[0]
        period = first_d - next_d # 강연갈 수 있는 일 수
        dCount = dCountList[str(first_d)] # 해당 기한으로 요청받은 강연 수
        # 기한이 넉넉하다면 모든 옵션들을 강연할 수 있다.
        if period >= dCount:
            for i in range(dCountList[str(first_d)]):
                option = feeList.pop(0)
                total += option[0] # fee 합산
        else:
            # dCount만큼 fee 기준으로 정렬한다. (같은 기한이므로 기한 정렬은 패쓰~)
            selected_options = sorted(feeList[:dCount], key=lambda option:option[0], reverse=True)
            extra_options = []
            # 기한이 부족할 경우 가능한 옵션 수만큼만 강연가고 나머지만 sort
            for i in range(dCount):
                if i < period:
                    # 기한 내
                    option = selected_options[i]
                    total += option[0]  # fee 합산
                else:
                    if next_d == 0:
                        break
                    else:
                        extra_options.append((selected_options[i][0], next_d))  # 초과하는 옵션들은 다음 기한으로 변경
            if next_d != 0:
                dCountList[str(next_d)] += len(extra_options) # 해당 기한의 옵션들의 수를 더 추가해준다.
            feeList = extra_options + feeList[dCount:]
    return total
 
 
if __name__ == "__main__":
    n = int(sys.stdin.readline())
    feeList = []
    dCountList = {} # 기한이 같은 옵션들의 수를 체크한다.
    dSet = set() # 제시된 기한들의 집합 값
    for i in range(n):
        p, d = map(int, sys.stdin.readline().strip().split())
        if str(d) in dCountList:
            dCountList[str(d)] += 1
        else:
            dSet.add(d)
            dCountList[str(d)] = 1
        feeList.append((p,d))
    dSet = sorted(dSet, reverse=True)
    print(greedy(feeList, dCountList, dSet))

---

실패한 코드 설명 - 남은 선택지의 기한을 1만큼 줄여나가기 (시간 초과)

제시한 기한(d)이 서로 다르면 강연 가는 날이 겹치지 않을테니 모든 강연을 다 받아들이면 된다. 

그러나 이 문제에서 해결해야 하는 문제상황은 제시한 기한이 동일하고 그 안에서 유리한 옵션들을 선택해 나가야 할때이다.

이 문제를 쉽게 해결하기 위해서 기한이 먼 옵션부터 차례로 선택해 나간다.

동일한 기한(d)이 제시된 옵션이 있다면, 강연비(p)가 높은 옵션 하나를 선택하고 남은 선택지의 기한을 1만큼 줄여준다. 

그리고 줄여진 기한과 동일한 옵션이 있다면 강연비(p)가 높은 옵션을 선택하면 된다.

그러고 남은 옵션들은 또다시 기한을 1만큼 줄여준다.  동일한 기한이 제시된 옵션이 없다면 

하나 남은 옵션을 선택해주고 그 다음 기한을 가진 옵션들을 찾아서 또다시 비교해주면 된다.

이 작업을 기한이 1일일때까지 (정확히 말하면 제시한 d가 젤 적은 옵션까지 조건을 비교했을 때까지) 반복하면 된다.

하지만..결과적으로 시간초과가 났다. d의 값이 큰 옵션이 여러개일 경우에는 정렬이 매우자주 일어나기 때문이다.

수도 코드 1 - 남은 선택지의 기한을 1만큼 줄여나가기 (시간 초과)

# 고려해야 하는 모든 옵션이 사라진다면 선택을 멈춘다.

total_fee = 0

sort optionList by p # 강연비를 기준으로 정렬

sort optionList by d in descending order # 기한을 기준으로 정렬 (python은 기존 정렬 순서를 최대한 유지하면서 다른 조건으로 정렬한다.)

while optionList:

# optionList는 기한별로 강연비가 가장 큰 옵션 순서로 정렬되어 있다.

 pop optionList[0] up and add total_fee

 if d is 1, break # 1일차에 갈 강연을 선택했으면 더 이상 다른 강연을 정렬할 필요가 없다.

 All remaining options are deducted by 1 by each option.

 Arrange options with same d (d is the reduced values)

return total_fee

파이썬 코드 1 - 남은 선택지의 기한을 1만큼 줄여나가기 (시간 초과)

import sys
 
def greedy(options):
    total_fee = 0
 
    # option은 항상 기한이 넉넉한 옵션 중에서 강연비가 높은 기준으로 정렬
    while options:
        selected = options.pop(0)
        total_fee += selected[0] # 선택한 강연료 합산
        if selected[1] == 1: # d가 1이면 더 이상 다른 옵션을 선택할 필요가 없음
            break
 
        same_d_index = -1
 
        for i in range(len(options)):
            # 이미 선택한 옵션의 기한과 같다면 기한을 1만큼 차감
            if selected[1] == options[i][1]:
                options[i] = (options[i][0], options[i][1] - 1)
                same_d_index = i
            # 1만큼 차감한 같은 경우에는 sort를 위해서 어디까지 같은 기한인지 i를 계산한다
            elif selected[1] - 1 == options[i][1]:
                same_d_index = i
                continue
            else:
                break
        # 정렬해야 하는 부분이 2개 옵션 이상 있으면 정렬
        if same_d_index > 0:
            # 필요한 부부분만 재정렬
            same_d_options = options[:same_d_index + 1]
            sorted_options = sorted(same_d_options, key=lambda option: option[0], reverse=True)
            options = sorted_options + options[same_d_index + 1:]
    return total_fee
 
 
if __name__ == "__main__":
    n = int(sys.stdin.readline())
    feeList = []
    for i in range(n):
        p, d = map(int, sys.stdin.readline().strip().split())
        feeList.append((p,d))
 
    feeList = sorted(feeList, key=lambda fee: fee[0], reverse=True)
    feeList = sorted(feeList, key=lambda fee: fee[1], reverse=True)
    print(greedy(feeList))
 
 

#2109 순회강연 #python 2109 순회강연 #백준 2109 순회강연 #백준 순회강연 #순회강연 #python 2109 순회강연 #백준 문제 풀이 #백준 순회강연 2109 #순회 강연 #백준 2109 순회강연

#백준 2109 순회강연 코드 #백준 2109 순회강연 python #python 백준 2109 순회강연