김낭만

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

백준(BOJ) 21397 긴 수 파이썬(Python)

문제 링크

수학 수열 문제.
조금 까다로울 수 있는데, 먼저 a=0인 경우(다만, 문제에서 1<=a<=10**6이므로 실제로 그런 케이스는 없다)를 상정하고 식을 세운 뒤, a!=0인 경우에 대해서 확장하는 방식으로 풀었다.
div는 자릿수가 d와 같거나 더 작은 수열의 항 개수를 의미한다.
digit은 b의 자릿수를 의미한다.
반복문을 돌며 수열의 숫자가 d자리일 때 나오는 항의 개수에 자릿수를 곱해서 c에서 빼주었다.
c가 충분히 작아지면(=현재 d자릿수 항 안에서 c를 구할 수 있으면) 항의 값을 구해서 모듈러 연산으로 자릿수를 찾아 숫자를 구해주면 된다.

#!python

from sys import stdin
from math import ceil, log10
input = stdin.readline

t = int(input())

for _ in range(t):
    a, b, c = map(int, input().split())

    # div는 d자리(또는 그 이하) 수의 수열의 항 개수
    # 처음에 d는 a의 자릿수와 같다
    div = ceil((10 ** int(log10(a) + 1) - a) / b)
    div_before = 0
    # digit은 b의 자릿수
    digit = int(log10(b))

    d, i= int(log10(a) + 1), 0

    # c가 속한 수열이 d자리보다 큰 동안
    while c > d * (div - div_before):
        # 처음에는 무조건 계산한다. 1번째 항이 a이기 때문
        # 그 이후에는 d가 b의 자릿수만큼 커진 후에 계산한다
        # div - div_before는 d자리 항의 개수
        # 따라서 d * (div - div_before)는 d자리 항이 수열에서 차지하는 숫자 개수이다
        if d >= digit or d == int(log10(a) + 1):
            c -= d * (div - div_before)
            i += div - div_before
        d += 1
        div_before = div
        div = ceil((10 ** d - a) / b)

    # 마지막에 남은 c를 d로 나눠서 몇 번째 항인지 구한다
    i += ceil(c / d)
    print(str(a + b * (i - 1))[c % d - 1])

2024

맨 위로 이동 ↑

2023

세그먼트 트리

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

벨만-포드 알고리즘

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

다익스트라 알고리즘

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

맨 위로 이동 ↑