김낭만

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

백준(BOJ) 1301 비즈 공예 파이썬(Python)

문제 링크

DP DFS 문제.
입력이 그다지 크지 않다는 데에서 DFS를 착안하는 것은 쉽다.
다만, 아무리 입력이 작다고 해도 완전탐색을 하면 시간초과가 난다.
생각해보면, i번째 구슬을 꿰는 상황일 때, 앞에서 사용한 구슬들이 순서와 상관없이 같고 거기에 더해 최근 사용한 2개의 구슬의 색깔도 같다면, 이후의 답은 동일할 것이다.
예를 들어, 앞에서 빨강-초록-파랑-노랑-빨강을 끼운 경우나, 초록-빨강-파랑-노랑-빨강을 끼운 경우나, 남은 구슬의 숫자 및 최근 사용한 2개의 구슬이 같으므로 부분문제의 답은 같을 것이다.
따라서, 메모이제이션을 활용하면 시간복잡도를 줄일 수 있다.
dfs()가 각 구슬의 개수와 최근 2개 구슬의 색깔(당연하지만 순서가 중요하다)을 인수로 받도록 하고 같은 인수를 받는 DFS에 대해 메모이제이션을 하면 쉽게 구현할 수 있다.
입력을 정렬하고 정렬된 순서에 맞게 색깔의 인덱스도 바꾼다면 겹치는 부분문제를 더 많이 캐싱할 수도 있을 거 같은데, 그렇게 안 해도 충분히 풀리기 때문에 하지는 않았다.

#!python

from functools import cache

# cache 데코레이터를 통한 메모이제이션
# args는 남은 구슬의 갯수, color는 최근 사용한 2개의 색깔
@cache
def dfs(*args, color):
    # 구슬이 없으면 경우의 수는 1개라고 정의
    if not any(args):
        return 1
    # 각 구슬에 대해
    # 그 구슬이 남아있고 이전 2개 구슬과 색이 다르다면
    # 그 구슬을 하나 빼서 넣고 재귀적으로 실행
    ans = 0
    for i, e in enumerate(args):
        if e and i not in color:
            ans += dfs(*(args[:i] + (e - 1, ) + args[i+1:]), color=(color[1], i))
    return ans

n = int(input())
orbs = [int(input()) for _ in range(n)]

# 처음엔 아무 구슬이나 넣을 수 있으므로 color를 n, n + 1로 두었다
print(dfs(*orbs, color=(n, n + 1)))

2024

맨 위로 이동 ↑

2023

세그먼트 트리

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

벨만-포드 알고리즘

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

다익스트라 알고리즘

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

맨 위로 이동 ↑