김낭만

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

백준(BOJ) 27172 수 나누기 게임 파이썬(Python)

문제 링크

한참을 고민했는데, 그냥 Straightforward한 방식(브루트 포스)가 정답이었던 어처구니 없는 문제.
TLE에 걸릴 거라 생각하고 고려조차 안 했던 방법이 정답인 뜬금없는 문제다.
더구나 시간을 재봤을 때, 꽤 작은 테스트 케이스에 대해서도 1초가 넘어서 당연히 그 방법은 아닐 거라 생각했는데, 백준의 Python 채점 시간 보정을 고려하면 충분히 통과할 수 있다.
아무튼, 방법은 간단하다. 크기 1000000의 배열에 카드의 수를 모두 넣어두고 각 카드에 대해서 배수를 모두 찾아주면 된다.

#!python

n = int(input())
nums = list(map(int, input().split()))

# is_in 배열은 존재하는 카드인지를 확인하는 배열
is_in = [False for i in range(1000001)]
for i in nums:
    is_in[i] = True

# 답이 저장되는 배열
arr = [0 for _ in range(1000001)]

# 그냥 전체 카드를 순회하면서
# 범위 내의 모든 배수를 찾아주면 된다
for num in nums:
    for j in range(num*2, 1000001, num):
        if not is_in[j]:
            continue
        arr[num] += 1
        arr[j] -= 1

print(*(arr[num] for num in nums))

2024

맨 위로 이동 ↑

2023

세그먼트 트리

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

벨만-포드 알고리즘

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

다익스트라 알고리즘

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

맨 위로 이동 ↑