[Python][백준] 7512번 연속하는 소수의 합

https://www.acmicpc.net/problem/7512

공부 날짜 : 2023.02.14
정답 참조 여부 : X

숫자 m개가 주어지며, 각 숫자를 ni라고 한다. (1 ≤ i ≤ m)

이때, 모든 i에 대해서, 연속하는 소수 ni개의 합으로 나타낼 수 있는 가장 작은 소수를 찾는 문제이다.

---

어찌어찌 풀긴했는데 왜 시간초과가 나지않았는지 이해가 되지 않고, 어디까지 조사를 해야하는지 이해가 잘 안됐던 문제이다.

일단 1부터 10^7 까지 소수를 판별하여 리스트를 만들었다.

---

그 다음 m개의 입력을 크기순으로 내림차순으로 정렬을 해준뒤
ni의 최대값인 [0]만큼 연속된 합을 구하며 소수인지 판단 했다.

그 다음 나머지 ni들에 대해서 [0]의 합과 비교하며 값이 작으면 구간을 넘기고,

같으면 다음 ni에 대해서 조사했다.

그러다가 값이 [0]보다 커지면 [0]의 구간을 다음 구간으로 바꿔서 전부 같아질때까지 반복 해 주었다.

---

어찌어찌 문제는 풀었는데, 이해가 안되는게 몇가지 있다.

1. 무조건 정답이 존재 하는가
   이 경우는 백준에서 주어지는 input에따라 결정되는 것이기 때문에 어떻게 되는것만 넣었겠지하고 넘겼다.

2. 다른 언어로는 어떻게 푸는가
   결론적으로 정답이 10^7까지였으니 10^7까지 소수 판별은 해야했다. (정답으로 나오는 수까지 전부 소수판별을 해야하기 때문) 그래서 무식하게 10^7까지 했지만, 다른언어에서 배열의 크기는 10만까지로 알고있는데.... 10^7까지 할려면 할수는 있지만 이게 의도한게 맞나 이해가 되지 않았다.

3. 왜 시간초과가 나지 않는가
   왜 아리토스테네스의 체 알고리즘이 O(nlog(logn))인가 잘 이해되지 않는다.... 자료를 찾아봤는데 이건 개인적으로 공부해서 이해해야 할거 같다.

문제 로직은 어렵지 않았는데 정답의 최대 크기가 너무 크다보니 겁먹어서 어렵다고 느낀 문제였다.

소스코드

import sys
input = sys.stdin.readline
#############################################
# 1부터 10e6 + 1까지 소수를 구해서 리스트로 만듬
max_num = 10000001

num = [True for _ in range(max_num)]

prime_num = []

for i in range(2, max_num):
    if num[i]:
        prime_num.append(i)
        for j in range(i+i, max_num, i):
            num[j] = False

count_prime = len(prime_num)

# print(prime_num)
# print(prime_num[-1])
# print(count_prime)
# print(sum(prime_num))

#############################################

t = int(input())

for test_case in range(1, t+1):
    m = int(input())
    count_num = list(map(int, input().split()))
    count_num.sort(reverse = True)

    sum_prime_num = [[sum(prime_num[:count_num[i]]), 0] for i in range(m)]

    while True:
        # 총 합이 소수인지 판별
        if num[sum_prime_num[0][0]]:
            break

        # 아니면 다음 구간의 합을 구해 줌
        sum_prime_num[0][0] -= prime_num[sum_prime_num[0][1]]
        sum_prime_num[0][1] += 1

        # 모든 경우를 해 봤지만 안되는 경우
        # 가... 있나?
        if sum_prime_num[0][1] >= count_prime - count_num[0] + 1:
            break

        sum_prime_num[0][0] += prime_num[sum_prime_num[0][1] + count_num[0] - 1]


    index = 1

    while True:
        # 모든 숫자가 같아진 경우
        if index == m:
            break

        # 0의 경우
        if index == 0:
            while True:
                # 아니면 다음 구간의 합을 구해 줌
                sum_prime_num[0][0] -= prime_num[sum_prime_num[0][1]]
                sum_prime_num[0][1] += 1

                # 모든 경우를 해 봤지만 안되는 경우
                # 가... 있나?
                if sum_prime_num[0][1] >= count_prime - count_num[0] + 1:
                    break

                sum_prime_num[0][0] += prime_num[sum_prime_num[0][1] + count_num[0] - 1]

                # 총 합이 소수인지 판별
                if num[sum_prime_num[0][0]]:
                    break

            index += 1
            continue

        # 값이 같아진 경우 다음 인덱스
        if sum_prime_num[index][0] == sum_prime_num[0][0]:
            index += 1
            continue

        # 값이 더 클 경우 0번 값의 구간을 바꿔줌
        if sum_prime_num[index][0] > sum_prime_num[0][0]:
            index = 0
            continue

        # 작은경우 이번 인덱스의 구간을 바꿔줌
        if sum_prime_num[index][0] < sum_prime_num[0][0]:
            sum_prime_num[index][0] -= prime_num[sum_prime_num[index][1]]
            sum_prime_num[index][1] += 1

            # 모든 경우를 해 봤지만 안되는 경우
            # 가... 있나?
            if sum_prime_num[index][1] >= count_prime - count_num[index] + 1:
                break

            sum_prime_num[index][0] += prime_num[sum_prime_num[index][1] + count_num[index] - 1]
            continue

    print(f"Scenario {test_case}:")
    print(sum_prime_num[0][0])
    print()