김낭만

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

백준(BOJ) 1039 교환 파이썬(Python)

문제 링크

간단한 DP 문제.
실질적인 m의 최대치는 6이고, \(_{6}C_{2} = 15\)이므로 단순한 완전탐색은 \(15^{10}\)으로 시간초과이다.
아이디어는, 어차피 숫자를 배열하는 경우의 수는 기껏해야 \(6! = 720\)가지이고, 즉 아무리 넓게 잡아도 \(720 \times 10 = 7200\)가지 문제에 대한 답만 알고 있으면 언제든지 입력에 대한 정답을 구할 수 있다는 것이다.
그러니까, 가능한 모든 경우를 탐색하다 DP 메모이제이션을 통해서 이미 구한 n과 k에 대해서는 다시 계산하지 않으면 된다.
추가로, 구현에 있어서 간편하게 functools.cache 데코레이터를 사용했고, 어차피 두 자연수 a와 b에 대해 자릿수가 같으면 a > b == str(a) > str(b)이므로 그냥 문자열을 그대로 사용했다.
그 외에 첫글자가 0이 되는 경우의 수를 제거해주는 것까지 체크하면 크게 어려울 것 없다.

#!python

from functools import cache

# 입력이 n, k일 때의 정답을 반환
# n, k가 동일하다면 무조건 답도 동일하므로 메모이제이션한다
@cache
def solve(n, k):
    # k == 0이면 바꿀 게 없으므로 n이 정답
    if not k:
        return n
    
    # 처음엔 '0'으로 이루어진 문자열로 초기화
    ret = zeros

    # 가능한 모든 경우 탐색
    for i in range(l):
        for j in range(i + 1, l):
            # s는 n[i], n[j]를 스왑한 문자열
            s = n[:i] + n[j] + n[i+1:j] + n[i] + n[j+1:]

            # 첫 글자가 0인 케이스는 안된다
            if s[0] == '0':
                continue

            # 가능한 경우 중 최대값을 반환
            ret = max(ret, solve(s, k - 1))

    # 초기화 이후로 문자열이 안 바뀜 == 바꾸는 게 불가능 == -1이 답
    return ret if ret != zeros else '-1'

# n은 문자열 그대로 처리해도 큰 상관 없다
# 어차피 같은 자리 양수 a, b에 대해 a > b == str(a) > str(b)임
n, k = input().split()
k = int(k)

# l은 총 자릿수, zeros는 정답 초기화를 위한 문자열
l = len(n)
zeros = '0' * l

print(solve(n, k))

2024

맨 위로 이동 ↑

2023

세그먼트 트리

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

벨만-포드 알고리즘

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

다익스트라 알고리즘

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

맨 위로 이동 ↑