[TIL_Carrotww] 116 - 23/06/01

📝Carrotww의 코딩 기록장

🧲 python algorithm

🔍 백준 소수의 연속 합

문제를 읽어보면 일단 주어준 값까지의 소수 리스트를 구해야한다는 것은 알것이다.
N이 주어졌을때 해당 값까지 소수를 구하는 것에대한 알고리즘은 에라스토테네스의 체 알고리즘이다.

def prime_list(n):
    is_prime = [True] * (n + 1)
    is_prime[0], is_prime[1] = False, False

    for i in range(2, int(n ** 0.5) + 1):
        if is_prime[i]:
            for j in range(i*i, n+1, i):
                is_prime[j] = False

    return [x for x in range(n+1) if is_prime[x]]

일단 이렇게 n이 주어지면 해당 값까지의 소수를 구했다.
다음 소수 리스트를 해당 길이로 리스트를 만들어서 해당 자릿수 까지의 합을 구한 리스트를 만들었다.
dp를 푼다고 생각하면 이해가 쉬울 것이다.

• 전체 풀이

def prime_list(n):
    is_prime = [True] * (n + 1)
    is_prime[0], is_prime[1] = False, False

    for i in range(2, int(n ** 0.5) + 1):
        if is_prime[i]:
            for j in range(i*i, n+1, i):
                is_prime[j] = False

    return [x for x in range(n+1) if is_prime[x]]

def solve():
    import sys
    num = int(sys.stdin.readline())
    primes = prime_list(num)
    sum_list = [0] * (len(primes) + 1)
    cnt = 0

    for i in range(1, len(primes) + 1):
        sum_list[i] = sum_list[i-1] + primes[i-1]

    for i in range(len(primes)):
        for j in range(i+1, len(primes)+1):
            if sum_list[j] - sum_list[i] == num:
                cnt += 1
            elif sum_list[j] - sum_list[i] > num:
                break

    print(cnt)

if __name__ == "__main__":
    solve()

골3 문제인데 솔직히 좀 까다로웠다 시간복잡도도 많이 신경써야하고...

다른 풀이도 있다
다른 사람들의 풀이를 보니 투 포인터로 풀 수 있다.

• 투 포인터

def solve():
    import sys
    num = int(sys.stdin.readline())
    if num == 1:
        print(0)
        return
    primes = prime_list(num)

    total = primes[0]
    start, end = 0, 0
    result = 0
    while end <= len(primes):
        if total == num:
            result += 1
            end += 1
            if end < len(primes):
                total += primes[end]
            else:
                break
        elif total < num:
            end += 1
            if end < len(primes):
                total += primes[end]
            else:
                break
        else:
            total -= primes[start]
            start += 1

    print(result)

if __name__ == "__main__":
    solve()

이렇게 풀면 조금 더 시간이 빠르게 나온다.
그리고 else: 부분에서 start += 1을 하여 end와 같아지면 어떡하지라고 생각을 하였는데 해당 문제에서 else 문이 실행됐다는 것은 주어진 수보다 total 값이 더 크다는 의미인데 주어진 값들은 최소 2개 이상을 합쳐야 total보다 커질 수 있으므로 start += 1 후에 start가 end와 같아질 것에 대한 if문은 안써도 된다.

5월달에 알고리즘 엄청 많이 풀었는데.. 이놈의 귀차니즘때문에 잘 안올렸다.. 최대한! 올려보자 후 오늘 끝!