김낭만

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

백준(BOJ) 1132 합 파이썬(Python)

문제 링크

가능한 가장 큰 합을 만드는 그리디(Greedy) 알고리즘 문제.
모든 십진수 \(n\)은 \(n_0 \times 10^0 + n_1 \times 10^1 + ... + n_k \times 10^k\)로 나타낼 수 있다는 걸 생각하면 쉽게 해결할 수 있다.
예를 들어 ABC는 1 * C + 10 * B + 100 * A이고, BCA는 1 * A + 10 * C + 100 * B이다.
이런 식으로 모든 수를 최대 10개 미지수의 합으로 나타낼 수 있다.
그렇다면 ABC + BCA는 어떻게 될까? 당연히 101 * A + 110 * B + 11 * C일 것이다.
가장 큰 값을 찾기 위해서는 가장 큰 수가 곱해진 미지수부터 9를 할당하고, 그 다음 수는 8을 할당하고, … 하는 식으로 0까지 할당하면 된다.
다만 0인 경우를 주의해야 하는데, 맨 첫 자리에는 0이 올 수 없기 때문에, 이러한 경우들을 미리 확인해준 후 그 수에는 0을 할당하지 않는 식으로 넘어갈 수 있다.
그렇게 할당한 수들을 전부 더해주면 최종적으로 정답이 나온다.

#!python

from sys import stdin
input = stdin.readline
INF = float('inf')

# count는 해당 알파벳이 더해진 횟수
# allow_zero는 해당 알파벳이 0일 수 있는지의 여부
n = int(input())
count = dict(zip('ABCDEFGHIJ', [0] * 10))
allow_zero = dict(zip('ABCDEFGHIJ', [True] * 10))
for _ in range(n):
    num = input().rstrip()
    # 가장 높은 자리의 숫자는 0이 될 수 없음
    allow_zero[num[0]] = False
    # 각 숫자의 자릿수만큼 count를 증가시킴
    for i, c in enumerate(reversed(num)):
        count[c] += 10 ** i

# count와 allow_zero를 편의상 밸류 리스트로 변경
ans = 0
count = list(count.values())
allow_zero = list(allow_zero.values())
# 0부터 9까지 순회
for num in range(10):
    # 최소값과 그 인덱스 알아내기
    min_val = INF
    min_idx = 0
    for i, e in enumerate(count):
        if min_val <= e:
            continue
        # 단, 0인 경우 allow_zero가 True인 숫자 중에서 최소값을 찾아야 함
        if num == 0 and not allow_zero[i]:
            continue
        min_val = e
        min_idx = i
    # INF인 경우는 break
    if min_val == INF:
        break
    # 정답에 해당 수를 더하고, 방금 찾은 최소값은 제거한다
    ans += num * min_val
    count[min_idx] = INF
print(ans)

2024

맨 위로 이동 ↑

2023

세그먼트 트리

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

벨만-포드 알고리즘

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

다익스트라 알고리즘

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

맨 위로 이동 ↑