김낭만

재밌거나 필요하다고 생각하는 걸 만듭니다.

백준(BOJ) 21943 연산 최대로 파이썬(Python)

문제 링크

입력이 작아서 그냥 완전탐색하면 되는 문제.
그런데 아무리 완전탐색이라지만 가능한 모든 경우를 보려고 하면 피연산자 최대 9개를 배치하기 위한 \(8!\), 연산자를 배치하기 위한 최대 \(_{9}C_{4}\), 거기에 괄호를 배치하는 경우까지 생각하면 무조건 시간 초과가 될 것이다.
여기선 연산의 종류가 덧셈과 곱셈이라는 점, 숫자들이 모두 양의 정수라는 점, 그리고 연산 순서를 마음대로 할 수 있다는 점에서 아이디어를 얻어서, 식을 곱셈을 기준으로 나눌 수 있다.
예를 들어 문제에서 든 예시 \((1+2+4+7) \times (5+8)\)는 하나의 곱셈을 기준으로 \((1+2+4+7)\)과 \((5+8)\)로 식이 나누어진 셈이다.
이제 문제는 q+1개로 나누어진 식(항이라고 보긴 애매하지만 편의상 그냥 항이라고 부르겠다)에 더할 수들을 배치하는 것이다.
최대 8개의 피연산자를 7개의 항에 넣는 것이므로 대략 \(56^8\)에 근사하게 되는데, 당연히 이 수도 엄청 큰 수이다.
이 부분은 어차피 항의 순서가 달라도 값들이 같다면 같은 결과가 나온다는 점에 착안하면 된다.
예를 들어서 \((1+2+4+7) \times (5+8)\)은 \((5+8) \times (1+2+4+7)\)과 동일하다.
따라서 이런 경우들을 처리하기 위해 항들을 담은 terms 튜플을 정렬해주고 메모이제이션을 사용해서 중복되는 계산을 없애주면 된다.
여기에서는 그렇게 하기 위해 @functools.cache 데코레이터를 사용했는데, 이건 함수가 호출되었을 때, 그 값을 미리 캐싱해두었다가 같은 인자로 함수가 호출되면 캐싱한 값을 돌려주는 함수이다.
즉, 메모이제이션을 간편하게 구현할 수 있는 방법이라 할 수 있다.
다만, 함수의 인자들이 모두 Hashable해야 한다는 제한이 있는데, 아마 딕셔너리로 구현이 된 게 아닌가 싶다.
그래서 함수의 인자로 리스트 대신 튜플을 사용했다.

#!python

from functools import cache, reduce

# cache 데코레이터는 메모이제이션을 해주는 함수
# dfs(nums, terms)가 호출될 때, 정확히 같은 매개변수로 호출된 적이 있으면 그 값을 그냥 돌려준다
# 대신, 인자들이 모두 hashable한 값이어야 한다(아마 딕셔너리를 사용하는 게 아닐까?)
# dfs(nums, terms)는 숫자들 nums와 각 덧셈으로 이루어진 항 terms에 대해 최적값을 돌려준다
@cache
def dfs(nums, terms):
    # 만약 숫자를 모두 사용했다면 terms의 각 항을 곱해서 반환
    if not nums:
        return reduce(lambda x, y: x * y, terms, 1)
    # 그렇지 않은 경우 반환값은 가능한 반환값 중 최대값
    ret = 0
    for i, e in enumerate(nums):
        # 각 숫자에 대해 반복
        # temp는 해당 숫자를 제외하고 남은 숫자들
        temp = nums[:i] + nums[i+1:]
        for j in range(q + 1):
            # 숫자 e를 j개의 항에 각각 넣어볼 것임
            # 이때, 항의 순서가 다르지만 내용이 같은 경우는 당연히 답도 같으므로 정렬해준다
            # 정렬하면 순서가 다른 terms가 모두 같은 튜플로 바뀌어서 메모이제이션한 값을 사용할 수 있다
            ret = max(ret, dfs(temp, tuple(sorted(terms[:j] + (terms[j] + e, ) + terms[j+1:]))))
    return ret

n = int(input())
x = tuple(map(int, input().split()))
p, q = map(int, input().split())
# terms는 곱셈을 기준으로 식을 나누고, 같은 terms 안에 있는 항들끼리는 더한다
terms = tuple(0 for _ in range(q + 1))

# 모든 숫자들에 대해, 각 항이 0일 때부터 시작
print(dfs(x, terms))

2024

맨 위로 이동 ↑

2023

세그먼트 트리

개요 선형적인 자료구조에서는 값에 접근하는 데에 \(O(1)\)이면 충분하지만, 대신 부분합을 구하는 데에는 \(O(N)\)이 필요하다. 그렇다면 이 자료구조를 이진 트리로 구성하면 어떨까? 값에 접근하는 데에 걸리는 시간이 \(O(\lg N)\)으로 늘어나지만 대신 부분합을 구하...

벨만-포드 알고리즘

개요 다익스트라 알고리즘과 함께 Single Sourse Shortest Path(SSSP) 문제를 푸는 알고리즘이다. 즉, 한 노드에서 다른 모든 노드로 가는 최단 경로를 구하는 알고리즘이다. 다익스트라 알고리즘보다 느리지만, 음수 가중치 간선이 있어도 작동하며, 음수 가중치 사...

다익스트라 알고리즘

개요 다익스트라 알고리즘은 Single Sourse Shortest Path(SSSP) 문제를 푸는 알고리즘 중 하나이다. 즉, 한 노드에서 다른 모든 노드로 가는 최단 경로를 구하는 알고리즘이다. 단, 다익스트라 알고리즘은 음수 가중치 엣지를 허용하지 않는다. 이 경우에는 벨만-...

맨 위로 이동 ↑