파이썬) 퇴사 -BOJ

https://www.acmicpc.net/problem/14501

14501번: 퇴사

 

문제 이해는 상당히 쉽다.

읽어보면 한 번에 이해가 되므로 문제 이해는 건너 뛰고,

이를 어떻게 풀 것인가를 나는 곰곰히 생각해보았다.

우선 n은 15 이하이다.

즉, 브루트포스를 이용해 풀어도 손쉽게 풀 수 있는 문제이다.

하지만 어떤 상담을 선택하고, 어떤 상담을 선택하지 않을지에 대해 다시 생각했다. 

브루트 포스와 선택과 선택 안함.

이 문제는 어디선가 보았던 문제와 상당히 비슷했다.

https://school.programmers.co.kr/learn/courses/30/lessons/43165

프로그래머스

바로 프로그래머스의 "타겟넘버" 문제이다.

타겟넘버는 주어진 숫자를 더하거나 빼 숫자 n을 만드는 문제이다. 이 문제 또한 주어진 숫자들을 모두 더하거나 빼거나 둘 중 하나를 선택해  타겟넘버 n을 만드는 문제이다.

해당 문제를 옛날에 풀었던 기억이 떠올라 dfs로 풀어봤다. 

코드를 작성하며 점점 이 알고리즘의 사용에 대해 확신을 갖게 되었고 무난하게 통과할 수 있었다.

 

n = int(input())

arr = []

for i in range(n):
    a = list(map(int, input().split()))
    arr.append(a)

max_price = 0


def dfs(idx, select, sum_price):
    if idx > len(arr)-1:
        return sum_price

    if select:
        if idx + arr[idx][0] - 1 > len(arr)-1:
            return sum_price

        sum_price += arr[idx][1]
        new_idx = idx + arr[idx][0]
        return max(dfs(new_idx, True, sum_price), dfs(new_idx, False, sum_price))

    else:
        if idx + 1 > len(arr)-1:
            return sum_price
        return max(dfs(idx+1, True, sum_price), dfs(idx+1, False, sum_price))


# def dfs(idx, select, sum_price):


print(max(dfs(0, False, 0),
      dfs(0, True, 0)))

코드는 위와 같다.

처음에 dfs함수를 두번 호출한다. 하나는 0번째 인덱스 상담을 선택한 것과 다른 하나는 선택하지 않은 것이다.

그리고 선택하지 않은 dfs함수에서 또 다음 인덱스 상담을 선택하지 않은 것과 선택한 dfs함수를 호출한다.

그리고 만약 상담이 arr의 갯수를 넘거나, arr의 마지막 번째가 하루만에 끝낼 수 있는 것이 아니라면 여태까지의 합산한 금액을 리턴하고, 

처음 dfs를 호출한 곳에서는 그 둘의 max값을 print해주면 된다.

주의할 점이라고는 "arr의 마지막 번째가 하루만에 끝낼 수 있는 것"이다.

여기서 왜 예제입력 2번이 통과되지 않은지 코드를 살펴보느라 5분은 낭비했었던 것 같다.