BAEKJOON 14501

02 May 2020

문제

입력

---

나의 처음 코드

브루트 포스와 적절한 조건을 잡으면 쉽게 풀 수 있는 문제이다. 문제에서 원하는 것은 상담사가 퇴직하기 전에 플렉스를 하기 위해 돈을 끌어다 모아야 해서, 비서가 스케줄을 가져다 줬다. 이 스케줄에서 소화할 수 있는 스케줄 다 뛰고 돈을 많이 벌자~ 이런 문제이다. 고려해야 될 상황은 현재 일(day)와 일을 했을 경우 걸리는 시간이다. 걸리는 시간이 주어진 N(퇴사일) 을 초과해서는 안된다. 그러면서 최대로 벌 수 있는 돈을 구해야한다. 코드는 다음과 같다.

N = int(input())
info_list = [0]
max_price = 0
for i in range(1, N+1):
    time, pay = list(map(int, input().split()))
    info_list.append((time, pay, i)) #시간 금액 인덱스 
 
def solution(info):
    global max_price
    queue = [info]
    while True:
        tmp_list = []
        for data in queue:
            next_idx = data[2] + (data[0] - 1)
            if next_idx <= N:
                for i in range(next_idx + 1, N+1):
                    now_info = info_list[i]
                    if now_info[2] + (now_info[0] - 1) <= N:
                        tmp_list.append((now_info[0], now_info[1] + data[1], now_info[2]))
            max_price = data[1] if max_price < data[1] else max_price
        queue = tmp_list    
        if len(queue) == 0:
            break

for i in range(1, N+1):
    if info_list[i][2] + (info_list[i][0] - 1) <= N:
        solution(info_list[i])

print(max_price)

문제 설명을 쓰고 내 코드를 보고나니,,,, 난 bfs로 풀었네? ㅋㅋㅋㅋㅋ 사실 두개 다로 풀어도 상관없을 것 같다. N의 최대값이 15이기도 하고, bfs로 풀었다 한들 어차피 전체 다 살펴보는 bfs를 썼기 때문이다. 문제가 쉬우므로 주석은 패~스~