Tag: math

def distance(x1, y1, x2, y2, r_squared):
    dist_sq = (x2 - x1) ** 2 + (y2 - y1) ** 2
    return dist_sq <= r_squared

def solve():

    N, R, D, X, Y = map(int, input().split())

    graph = [[0, 0]]
    for _ in range(N):
        graph.append(list(map(float, input().split())))

    v = [False] * (N + 1)
    
    q = deque([(X, Y, 0)])
    
    result = 0.0
    
    r_sq = R * R

    while q:
        cur_x, cur_y, count = q.popleft()

        for i in range(1, N + 1):
            target_x, target_y = graph[i]

            if not v[i] and distance(cur_x, cur_y, target_x, target_y, r_sq):
                v[i] = True

                result += (D / (2 ** count))
                
                q.append((target_x, target_y, count + 1))

    print(result)
solve()

def bfs(n):
    q = deque([1])
    while q:
        cur = q.popleft()
        for n_num in (cur * 10 + 0, cur * 10 + 1):
            if len(str(n_num)) > 100:
                continue
            
            if n_num % n == 0:
                return n_num
            q.append(n_num)

while True:
    n = int(input())
    if n == 0:
        break

    print(bfs(n))

O(2^100) (worst case, but pruned by modulo check)

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

ans = n - 2

# 모든 가능한 두 카드 조합 (i, j)에 대해 확인
for i in range(n):
    for j in range(i + 1, n):
        if (cards[j] - cards[i]) % (j - i) != 0:
            continue
        d = (cards[j] - cards[i]) // (j - i)
        cnt = 0
        
        for k in range(n):
            expected = cards[i] + (k - i) * d
            if cards[k] != expected:
                cnt += 1
        
        ans = min(ans, cnt)

print(ans)

from collections import Counter, defaultdict

input = sys.stdin.readline
print = sys.stdout.write

N = int(input())

students = [int(input()) for _ in range(N)]
MAX_STUDENT = max(students) + 1

counter = Counter(students)
toktok = defaultdict(int)

for i in range(1, MAX_STUDENT):
    for j in range(i, MAX_STUDENT, i):
        if j in counter:
            toktok[j] += counter[i]

print("\n".join(str(toktok[s] - 1) for s in students) + "\n")

rope = []
for i in range(0, n):
    rope.append(int(input()))

rope.sort(reverse=True)
max_w = 0
for cnt, r in enumerate(rope):
    if max_w <= r * (cnt + 1):
        max_w = r * (cnt + 1)

print(max_w)

반복문을 돌면서 (로프의 개수) * (지금 확인한 로프의 무게)의 값이 저장해 놨던 무게 max_w 보다 크면 max_w를 바꿔준다.

dynamic programing으로 접근해 보면 조약돌의 오른쪽에서 작업을 시작하여 각 자리마다 그 때의 최소 작업 횟수를 저장하여 memoization할 수 있다.

하지만 단순히 이전까지의 최소 작업 횟수에 현재 자리의 최소 작업을 더한다고 최종적인 최소 작업 횟수가 될 수는 없다. 아래와 같은 예를 보자.

조약돌의 개수가 위와 같이 주어졌을 경우 두 번째 자리까지 최소 횟수는 2이다. 이를 저장하고 다음으로 넘어가서 마지막 자리인 두 개의 조약돌을 빼내는 횟수 1을 단순히 더하면 총 횟수는 3회이다.

하지만 처음부터 1번 작업으로 모두 진행하게 되면 두 번 만에 끝낼 수 있다.

예를 들면 55-50+40+90-100+10-11 이라는 수식이 입력됐을 때 55-(50+40+90)-(100+10)-11 = 55-50-40-90-100-10-11 로 만들 수 있다.

st = input().strip()+ '+'
total = 0
minus = False
num = ''
for c in st:
    if c.isdigit():
        num += c
    else:
        if minus:
            total -= int(num)
        else:
            total += int(num)
        if c == '-':
            minus = True
            
        num = ''
print(total)

입력은 숫자와 부호가 섞인 문자열로 주어지기 때문에 그 문자열을 확인하면서 문자가 숫자인지 부호인지에 때라 다르게 처리를 해주어야 한다.

def dp(b1, b2, n, m):
    global memo
    if b1 == n:
        return 1
    cnt = 0
    for i in range(b2 + 1, min(m, b2 + m - n + 1) + 1):
        if (b1 + 1, i) in memo:
            cnt += memo[(b1 + 1, i)]
        else:
            tmp = dp(b1 + 1, i, n, m)
            cnt += tmp
            memo[(b1 + 1, i)] = tmp
    return cnt

t = int(input())
for _ in range(t):
    memo = {}
    n, m = map(int, input().split())
    print(dp(0, 0, n, m))

ring = list(map(int, input().split()))
first = ring[0]
rings = ring[1:]
def gcd(a, b):
    while a % b != 0:
        r = a % b
        a, b = b, r
    return b

for r in rings:
    if first % r == 0:
        print(f"{first // r}/1")
    elif r % first == 0:
        print(f"1/{r // first}")
    else:
        g = gcd(first, r)
        print(f"{first // g}/{r // g}")