백준 14051번 : 퇴사 (feat. Python)

문제

간단하게 문제를 설명하자면 백준이가 퇴사하려는데 돈을 많이 받고 싶어서 남은 N일 동안 많은 상담을 잡기로 하는데 각 상담에는 상담 완료하는데 걸리는 시간 Ti과 받을 수 있는 금액 Pi가 있다. 이러한 제한조건을 기반으로 백준이는 퇴사 전까지 최대 수익을 구해야 한다.

여기서 최대 수익을 얻는 방법은 아래와 같다.

최대수익 = P1 + P4 + P5

예제

7
3 10
5 20
1 10
1 20
2 15
4 40
2 200

45

위 예시를 보면 몇 개의 케이스가 나올까?

• solution(0) = 10 + 20 + 15 <- 3 / 3, 1 / 3, 2 / 3, 1, 2
• solution(1) = 20 <- 5
• solution(2) = 10 + 10 + 15 <- 1 / 1, 1 / 1, 2 / 1, 1, 2
• solution(3) = 20 + 15 <- 1 / 1, 2

10
5 50
4 40
3 30
2 20
1 10
1 10
2 20
3 30
4 40
5 50

• solution(0) = 50 + 10 + 30 <- 5 / 5, 1 / 5, 2 / 5, 3 / 5, 1, 2 / 5, 1, 3

나만의 문제 해석

첫째 줄에는 1 <= N <= 15로 일할 수 있는 기간이 존재
최대수익 = Pa + Pb + ... + Pn
시간 = 모든 시간의 합 < N+1

위 예시를 이용해 처음에 index 0을 선택한 경우 배열 3부터 N 사이로 시작할 수 있음. 근데 여기서 기존에 선택한 index 0에서의 가격 + 3~N 사이의 선택한 가격 + k~N으로 선택한 가격 + ... 이런식으로 이어짐을 알 수 있음

언제 그만 두니!? 시작 날짜 + 상담날짜가 N보다 큰 경우에 상담을 그만두게 된다. 그리고 위 예시에서 알고리즘이 움직이는 방식을 보면 순서가 있는 순열과 조합 느낌이 많이 난다. 만약에 N이 7이면 시간의 합이 7이 넘지 않는 조합이자 구간이 정해져 있음

1. 과정 속에 조건을 넣어 맞는 조합을 만들것인가? - 해봤는데 실패함
2. 조합 전체를 생성하고 조건에 맞지 않는 것을 걸러낼 것인가? - 성공

공통 함수

# 일할 수 있는 시간
can_work_day = int(input())

# 상담 배정 배열
consultings = []

# 최대 수익
max_benefit = [0 for i in range(0, can_work_day)]

# 상담 예약 날짜를 2차원 배열로 형성
for i in range(0, can_work_day):
    consult = list(map(int, input().split( )))
    consultings.append(consult)

1번 케이스 : 과정 속에 조건을 넣어 맞는 조합을 생성 - 어렵고 실패함

def solution(x, y):
    # 만약 상담 걸리는 시간 + 시작 날짜가 N보다 크면 실행할 수 없음
    if (x + consultings[x][0]) > can_work_day:
        return y
    
    for i in range(x, can_work_day):
        print(x, y + consultings[i][1])
        if (i + consultings[i][0]) < can_work_day:
            return solution(x + consultings[i][0], y + consultings[i][1])
        elif (i + consultings[i][0]) == can_work_day:
            return y + consultings[i][1]

# j는 시작점을 말함
for j in range(0, can_work_day):
    benefit = solution(j, j, 0, 0)
    max_benefit[j] = max(case_benefit[j])

print(max(max_benefit))

2번 케이스 : 조합을 생성하고 조건에 맞게 거르기

from itertools import chain, combinations

# index 배열
index_array = [i for i in range(0, can_work_day)]

# 무작위 조합 생성
index_location = list(chain.from_iterable(combinations(index_array, i) for i in range(0, len(index_array)+1)))

max_value = 0

# 조합 배열에서 하나를 뽑아서 다른 걸 진행
for i in index_location:
    # 시간 초과 체크
    time_sum = 0

    # 간격 체크
    is_valid = True

    # 여기서의 max_value 함산
    value = 0

    # 길이가 1인 경우 그게 가장 큰 경우
    if len(i) == 1 and (consultings[i[0]][0] + i[0]) <= can_work_day:
        max_value = max(max_value, consultings[i[0]][1])
    # 길이가 1보다 큰 경우
    elif len(i) > 1:
        # 앞뒤 시간 간격 체크
        for j in range(0, len(i)):

            # 예를 들어, i = (0, 3)이면 3 + 0 > 다음 요소 이면 False 인데 다음 요소는 len(i)보다 작아야 한다. 간격이 맞아야 함
            if (j + 1) < len(i):
                if (consultings[i[j]][0] + i[j]) > i[j + 1]:
                    is_valid = False
                    break
            
            # 마지막 요소가 타임라인이 근무시간을 넘어가는 경우
            if (j + 1) == len(i):
                # 현재 위치 + 근무기간 : 9 + 1 = 10 
                if (consultings[i[j]][0] + i[j]) > can_work_day:
                    is_valid = False
                    break
                else:
                    is_valid = True
                    pass
            
            value += consultings[i[j]][1]
            
    # 모든 조건이 성립할 경우
    if is_valid:
        max_value = max(value, max_value)
    

print(max_value)