99클럽 - N개의 최소공배수, 연속 부분 수열 합의 개수

N개의 최소공배수

프로그래머스

아이디어

(작성중)

풀이

def gcd(x, y):
    while y:
        x, y = y, x % y
    return x

def lcm(x, y):
    return x * y // gcd(x, y)

def solution(arr):
    answer = arr[0]
    
    for num in arr[1:]:
        answer = lcm(answer, num)

    return answer

 

연속 부분 수열 합의 개수

프로그래머스

아이디어

(작성중)

풀이

def solution(elements):
    n = len(elements)
    prefix_sum = [0] * (2 * n + 1)
    
    for i in range(1, 2 * n + 1):
        prefix_sum[i] = prefix_sum[i - 1] + elements[(i - 1) % n]
    
    sums = set()
    for start in range(1, n + 1):
        for end in range(start, start + n):
            sums.add(prefix_sum[end] - prefix_sum[start - 1])
    
    return len(sums)