김낭만

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

백준(BOJ) 1082 방 번호 파이썬(Python)

문제 링크

간단한 DP 문제.
임의의 비용을 사용하는 부분문제가 중복되어 등장하므로 쪼개어 풀면 된다.
0을 제외하고는 맨 앞에 0이 올 수 없다는 점에 유의해야 한다.
또한, 0이 연속될 때, 수치적으로는 다른 수보다 작아도 앞에 다른 수가 붙으면 더 커질 수 있음에 유의해야 한다.
이를테면, 000은 1보다 작지만, 1000은 11보다 크다.
사실, 이 두 문제를 해결하려면 그냥 숫자를 앞이 아니라 뒤에 붙이면 되는데, 그 생각을 못해서 숫자를 앞에 붙여나가느라 조금 트리키했다.
즉, 000을 1000으로 만들어 나가는 것보단, 100을 1000으로 만들어가는 식으로 접근하는 게 훨씬 낫다는 것.
문제를 풀기 전에 항상 생각을 하는 게 중요하다는 것을 새삼 느꼈다.
아무튼, 연속되는 0의 문제를 해결하기 위해 intmax와 strmax라는 두 가지 함수를 만들었다.
intmax는 두 문자열 중 정수로 변환하면 더 큰 값을 반환하고, strmax는 두 문자열 중 더 긴 것(길이가 같다면 값이 더 큰 것)을 반환한다.
부분문제를 해결할 때는 앞에 숫자가 붙을 수 있으므로 strmax를 쓰고, 최종적인 정답은 수치상 더 커야 하므로(즉, 000이 아니라 1이 정답이 되어야 하므로) intmax를 썼다.
근데 그냥 전술한 것처럼 숫자를 앞이 아니라 뒤로 붙였으면 훨씬 간단하게 풀었을 듯…

#!python

# dp 위한 cache 데코레이터
from functools import cache

n = int(input())
p = list(map(int, input().split()))
m = int(input())

# intmax: a와 b중 정수로 변환하면 더 큰 값 반환
# strmax: a와 b중 앞에 숫자가 붙으면 더 커지는 값 반환
intmax = lambda a, b: b if a == '' else a if int(a) >= int(b) else b
strmax = lambda a, b: intmax(a, b) if len(a) == len(b) else a if len(a) > len(b) else b

# solve(m, flag): 비용 m을 사용해서 만들 수 있는 제일 큰 수
# flag는 True면 intmax를, False면 strmax를 수행한다
@cache
def solve(m, flag):
    ret = ''
    for i in range(n):
        if m < p[i]:
            continue
        if flag:
            getmax = intmax
        else:
            getmax = strmax
        ret = getmax(ret, str(i) + solve(m - p[i], False))
    return ret

print(int(solve(m, True)))

2024

맨 위로 이동 ↑

2023

세그먼트 트리

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

벨만-포드 알고리즘

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

다익스트라 알고리즘

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

맨 위로 이동 ↑