[Python] 15711번 : 환상의 짝꿍

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

15711번: 환상의 짝꿍

 

문제 3줄 요약

1. 두 사람은 각각 인연의 증표로 끈을 갖고 있다.

2. 두 끈을 이어붙이고 다시 길이가 소수인 끈 두개로 정확히 나눈다.

3. 나누는 것이 가능하다면, 환상의 짝꿍!

 

 

---

 

오늘도 저번 골드바흐의 추측에 이어

소수와 관련된 문제를 풀고자한다.

 

2023.03.07 - [프로그래밍 공부/백준 알고리즘] - [Python] 6588번 : 골드바흐의 추측

[Python] 6588번 : 골드바흐의 추측

 

 

골드바흐의 추측에서는

N이 최대 100만 이었지만,

환상의 짝꿍의 끈의 최대 길이는 무려 2*10^12 다.

 

두 끈을 합친다면,

최대 4*10^12 인 셈이다.

 

소수를 구하기 위해서

당연하게도

에라토스테네스의 체를 이용하였다!

 

from sys import stdin

# 테스트케이스
T = int(stdin.readline())

# max : sqrt(4*10^12, 2)
max = (2*(10**6))+1

# num_list : 소수를 담을 리스트
# visited : 소수 제외 판정
num_list, visited = [], [True] * (max+1)
visited[0], visited[1] = False, False

for i in range(2, max):
    if visited[i] == False:
        continue
    num_list.append(i)

    for j in range(i*2, max, i):
        visited[j] = False

 

---

소수를 구했으니,

더한 값이 소수의 합으로 나눠지는지 알아보자!

 

골드바흐의 추측을 이용하여,

4 이상인 짝수는 "YES" 출력하며, 통과한다.

 

소수로 나눠지는 경우가 또 있을까?

 

골드바흐의 추측을 벗어나는

홀수 + 짝수 = 홀수,

인 경우에 홀수와 짝수가 모두 소수인지 확인해보면 된다.

 

여기서 짝수인데 소수인 경우는?

2 가 유일하다.

 

따라서

 

S-2 가 소수면,

소수로 나누는 것이 가능해진다.

 

소수 판정에 사용하였던 리스트를 이용해

O(1)의 시간복잡도로 S-2가 소수인지 아닌지 판별한다.

 

여기서 한가지 문제..

S-2가 우리가 구했던 소수 판정 범위는

sqrt(4*10^12, 2) → 2*10^6

 

범위를 넘게되면,

반복문을 통한 소수의 나머지를 이용하여 소수인지 아닌지 판별한다.

 

for _ in range(T):
    x, y = map(int, stdin.readline().split())
    sum = x+y
    # 골드바흐의 추측
    # 4 이상인 짝수는 모두 소수의 합으로 나눠진다.
    if sum < 4:
        print("NO")
        continue

    if sum%2 == 0:
        print("YES")
        continue

    # 합이 소수로 나눠지는지 판별
    # S-2가 소수 판정 범위 안인 경우
    chk, sum = 1, sum-2
    if sum < max:
        if visited[sum]:
            print("YES")
        else:
            print("NO")
        continue

	# S-2가 소수 판정 밖인 경우
    for i in range(0, len(num_list)):
        if sum % num_list[i] == 0:
            print("NO")
            chk = 0
            break

    if chk:
        print("YES")

---

정답률이 16%인 만큼,

머리 아픈 문제였다..

 

다음 문제 또한 소수를 사용한 문제를 풀어보도록 하겠다.

 

끝!