(Python/🥇3)백준알고리즘 15711번: 환상의 짞꿍

 

문제 바로가기 

백준알고리즘

문제:

환상의 나라 디디랜드에서는 인연의 증표로 끈을 하나씩 가지고 있다. 그들은 지극히 평범한 방법으로 이 끈을 이용하여 어떤 두 사람이 환상의 짝꿍인지 판단하는데, 두 사람의 끈을 서로 이어붙이고 그 끈을 다시 길이가 소수인 끈 두개로 정확히 나눌 수 있다면 두 사람은 환상의 짝꿍이라고 한다. 하지만 그들은 길이가 소수인 두개의 끈으로 나눌 수 있는지 판단하는 것이 어려워서 대부분 서로가 인연임을 모르고 그냥 지나간다고 한다. 애석하게도... 그런 그들을 위해서 어떤 두 사람이 환상의 짝꿍인지 판단하는 프로그램을 작성하라. 편의상 두 사람의 끈을 이어붙일 때와 나눌 때 손실되는 끈의 길이는 0이라고 가정한다.

입력:

 

첫째 줄에 테스트 케이스의 수 T(1 ≤ T ≤ 500)가 주어진다. 둘째 줄부터 T개 줄에 두 사람이 가지고 있는 끈의 길이를 나타내는 정수 A, B가 공백으로 구분되어 주어진다. (1 ≤ A, B ≤ 2 × 1012)

출력:

각 테스트 케이스마다 한 줄씩 두 사람의 끈을 이어붙이고 그 끈을 다시 길이가 소수인 두개의 끈으로 정확히 나눌 수 있다면 YES, 불가능하면 NO를 출력하라.

풀이:

import sys
sys.stdin = open('/Users/song/Desktop/Python/Python/h.txt', 'r')

T = int(sys.stdin.readline())
board = [True] * (int(2*1000000000000000 ** 0.5) + 1)
board[1] = False
m = int(2*1000000000000000 **0.5)
for i in range(2,m+1):
    if board[i]:
        for j in range(i**2,m+1,i):
            board[j] = False
for i in range(T):
    A,B = map(int,sys.stdin.readline().rstrip().split())
    if (A+B) % 2 == 0:
        print("YES")
        break
    if board[A] == True and board[B] == True:
        print("YES")
    else:
        sum = A+B
        for i in range(2,sum//2+1):
            if board[i] ==True and board[sum-i] == True:
                print("YES")
                break
            print("NO")

 

틀린 시도

 

에라어쩌구 체로 일단 걸러주고 

일단 두 숫자가 짝수면 무조건 된다. 골드바흐의 추측 때문에된다.

두 숫자가 둘다 홀수이면 그것도 마찬가지로 된다. 홀수의 합으로 이루어진거기 떄문에.

 

그게 아닐때는 하나씩 확인을 해줘야한다

import sys
sys.stdin = open('/Users/song/Desktop/Python/Python/h.txt', 'r')

T = int(sys.stdin.readline())
board = [True] * (2000001)
board[1] = False
m = int(2000000)
lst = []
for i in range(2,m+1):
    if board[i]:
        lst.append(i)
        for j in range(i*2,m+1,i):
            board[j] = False

def check(num):
    try:
        if board[num]:
            return True
        else:
            return False
    except:
        for i in lst:
            if num % i == 0:
                return False
        return True

for i in range(T):
    S = sum(map(int,sys.stdin.readline().rstrip().split()))
    if S < 4:
        print("NO")
    elif S % 2 == 0:
        print("YES")
    else:
        if check(S-2):
            print("YES")
        else:
            print("NO")

 

45 프로에서 시간 초과 남

 

 

import sys

# 소수판정
def is_prime(value) :
    if value > max_value :
        for prime in primes :
            if prime >= value :
                break
            elif value % prime == 0 :
                return False

        return True
    else :
        return data[value]

# 에라토스테네스의 체
max_value = 2000000
data = [False, False] + [True for _ in range(max_value-1)]
primes = []
for i in range(2, max_value + 1) :
    if data[i] :
        primes.append(i)
        for j in range(i+i, max_value, i) :
            data[j] = False

# 구현
T = int(input())
for _ in range(T):
    S = sum(map(int,sys.stdin.readline().rstrip().split()))
    if S < 4:
        print('NO')
    elif S % 2 == 0:
        print('YES')
    elif is_prime(S-2):
        print('YES')
    else:
        print('NO')

아니 이렇게까지 해야하나 싶은 문제인데 이렇게 해야 정답이 남  심저이 pypy3으로 내야함

https://velog.io/@dlrjs2360/%EB%B0%B1%EC%A4%80-PyPy3-%EA%B3%A8%EB%93%9C3-15711-%ED%99%98%EC%83%81%EC%9D%98-%EC%A7%9D%EA%BF%8D

[ 백준 / PyPy3 ] [골드3] 15711 - 환상의 짝꿍

 

그냥 패스