Python으로 푸는 백준 14501. 퇴사

백준 14501. 퇴사

 백준이가 퇴사를 하기 전, 최대한 많은 상담을 진행하여

백준이가 상담으로 얻을 수 있는 최대 이익을 구할 수 있도록 개발해야 한다.

백준에서 푼 문제 리스트 보기

백준에서 문제 보기

github에서 코드 보기

문제 조건

백준이는 비서에게 최대한 많은 상담을 잡으라고 했다.

각각의 상담을 완료하는데 걸리는 시간은 각각 Ti에 적혀 있다.

모든 상담을 N일째 되는날 진행할 수 있다.

상담의 시작 날짜를 조정할 순 없고, 다만 상담을 할지 말지 여부만 결정할 수 있다.

문제 풀이

나는 비트마스크를 활용하여 모든 경우의 수를 탐색하여 문제를 풀었다. 주어진 조건에 따라서 가지치기를 하면서 최대 금액을 계산하였다.

내가 가지치기를 한 조건은 다음과 같다.

1. 남은 퇴사일이 상담을 진행해야 하는 일수보다 적어 상담을 진행할 수 없는 경우

2. 이미 상담을 진행중이어서 오늘 날짜에는 상담을 진행 할 수 없는 경우

비트마스크를 활용하는 방법을 이해하고 있고, 위의 조건이 코드에서 어떻게 구현 되었는지 알아볼 수 있다면 내 알고리즘을 완벽하게 이해 하였다고 볼 수 있다. 

코드 리뷰

근데 다른 사람들이 파이썬으로 풀었을 때의 소요시간을 보니, 내 코드가 그닥 효율이 좋아보이지 않는다.

당연한 게, 나는 브루트포스 방식으로 모든 경우의 수를 탐색했고, 이 문제는 충분히 다이나믹 프로그래밍 방식으로도 풀 수 있다. 

그래서 추후에 다이나믹 프로그래밍 방식으로도 이 문제를 해결하여 파이썬 코드를 덧붙이도록 하겠다.

파이썬 코드

 
# 모든 경우의 수를 구하고 그 안에서 답을 찾는다
def solve(n, tlist, plist):
 
    max_fee = 0
    for i in range(0, 1 << n):
        d = n  # 남은 퇴사일
        result = 0
        counsel_d = 0
        for j in range(0, n):
 
            if i & (1 << j):
                # counsel is over
                if counsel_d == 0:
                    # 남은 퇴사일보다 남은 상담 환자들의 상담기간이 적을 경우
                    if d >= tlist[j]:
                        # 상담 진행
                        counsel_d = tlist[j]
                        result += plist[j]
 
            # 상담이 예정되어 있으면 상담 진행
            if counsel_d:
                counsel_d -= 1
            d -= 1 # 하루가 흘러감
 
        if max_fee < result:
            max_fee = result
    return max_fee
 
 
if __name__ == "__main__":
    n = int(input().strip())
    tlist = []
    plist = []
    for i in range(n):
        t, p = input().strip().split()
        tlist.append(int(t))
        plist.append(int(p))
    print(solve(n, tlist, plist))

#백준 14501 퇴사 #백준 14501 python #백준 퇴사 #파이썬 백준 퇴사 #파이썬 백준 14501