[python] 백준 boj2109 순회강연 (아마도 그리디 풀이법)

 

1. 문제 요약

 

순회강연 🟡 3

(자세한 문제는 링크에서 확인!)

 

한 저명한 학자에게 n개의 대학에서 강연 요청이 옴(0 <= n <= 10000)

각 대학에서는 d(1 ≤ d ≤ 10,000)일 안에 와서 강연을 해 주면 p(1 ≤ p ≤ 10,000)만큼의 강연료를 지불

가장 많이 벌 수 있을 땐 얼마?

 

2. 설계

 

최근 그리디 알고리즘을 배우는 중이다.

말이 어려워서 그렇지 그리디 알고리즘이란 '직관적'으로 풀어낸 알고리즘을 말한다.

이 직관이 먹히는 직관인지, 아닌 직관인지는 문제마다 달라질 수 있고..ㅎㅎ

그 와중에 정형화된 알고리즘들이 있는데(ex. 다익스트라)

아직 그건 내가 배우기 전이고, 이 문제는 그리디 문제인 것 같아서 무지성(?) 코드를 짜기로 했다.

 

최근 수업시간에 비슷한 문제를 풀었던 것 같아서, 그 때의 논리를 더듬어 설계했다.

그 문제는.. 활동 선택(Activity-selection problem) 문제였다.

 

1. 강연 요청들을 list로 받아서, 기한(d)을 기준으로 내림차순 정렬한 후

2. 기한이 가장 먼 요청부터 할당하기

    -1. 해당 기한에 들어올 수 있는 모든 후보군을 추려서

    -2. 후보군 중에서 가장 강연료(p)가 높은 요청을 선택

    * 강연요청들이 내림차순으로 정렬되어있으므로, 적절하게 가지치기해주기

 

 

3. 삽질기

 

1. 채점 100%에서 런타임에러(ValueError)가 뜨는 이슈

n개의 대학에서 요청이 오는데, 문제는 n의 범위가 n >= 0 이기 때문에 n=0으로 input이 들어올 수 있었다.

이 경우엔 당연히 output으로 0이 출력되어야 하고,

코드 내에서는 이걸 처리할 방법이 딱히 떠오르지 않아서

if문으로 처리해버렸다...ㅋㅋㅋㅋㅋㅋㅋㅋ

 

 

2. 쓸모없는 코드

# request 할당할 work 배열 생성(리스트 길이는 최대인 d)
# 이미 할당한 request 를 체크 하기 위한 used 배열 생성
work_n = max(requests[x][1] for x in range(n))
work = [0] * (work_n + 1)  # 이거 안 써서 필요 없음...
used = [0] * n
fee = 0

원래 이 문제는 우리 스터디 문제라서,

나중에 스터디원들이랑 코드 리뷰할 때 가독성 좋으라고 주석을 열심히 다는 도중에

work 배열이 혼자 놀고 있는 사실을 발견했다.

(원래는 예쁘게 스케줄링하려고 만든 배열이었다...ㅋㅋ)

 

달랑 코드 한 줄이지만 input값에 따라 꽤 큰 배열이 될 것 같아서 지우고 다시 돌려보니

10% 정도 실행 속도가 빨라졌다.

 

요렇게 ㅇㅅㅇ

 

 

4. 최종 코드

n = int(input())  # n = 0인 악랄한 인풋이 채점 100%대에 서식중
if n != 0:
    requests = [list(map(int, input().split())) for _ in range(n)]
    # 기한이 긴 순서대로 requests 정렬
    requests.sort(key=lambda x: -x[1])

    # 이미 할당한 request 를 체크 하기 위한 used 배열 생성
    work_n = max(requests[x][1] for x in range(n))
    used = [0] * n
    fee = 0

    # 가장 기한이 긴 것부터 할당 시작
    for i in range(work_n, 0, -1):
        # 들어갈 수 있는 후보를 담을 배열
        candidates = []

        # 후보 찾기
        for j in range(n):
            if requests[j][1] >= i:
                if not used[j]:
                    candidates.append((requests[j][0], j))
            # 기한 큰 순서대로 정렬했기 때문에 위 조건에 맞지 않으면 promising 하지 않음
            else:
                break

        # 후보 중 가장 돈 많이 주는 request를 할당하기
        max_p = idx = 0
        for k in range(len(candidates)):
            if candidates[k][0] > max_p:
                max_p = candidates[k][0]
                idx = candidates[k][1]
        fee += max_p
        used[idx] = 1

    print(fee)
else:
    print(0)

 

5. 느낀 점

 

나는 2000ms 대의 실행시간이  걸렸는데,

같은 python 코드라도 100ms도 되지 않는 분들이 있었다.

이제는 문제가 주어지면 어떻게든 꾸역꾸역꾸역 풀어낼 수는 있는 것 같으니까

앞으로는 최적화를 고민해봐야곘당....

 

근데 C++은 도대체 어떤 언어길래 한 자릿수 실행시간이지..^^....?

역시 기계어에 가까운 건 다르구먼.....!