9020 골드바흐의 추측 풀이(진행중)

2024/01/13
처음 문제를 보고 생각이 든건

1. input으로 들어온 수를 list에 넣어야겠다
2. 매개변수로 넣어준 int 변수를 for문으로 돌려 1~변수값 중 소수인 값을 찾아서 리스트에 넣어준 후 return 시킨다.
3. 넘어온 리스트 값에서 더하면 목표값이 나오는 요소를 또 list에 넣어주고 차이가 적은 수를 출력한다.

그렇게 해서 나온 코드

def PrimeNumber(a):
    list = []
    if a == 1:
        return
    
    for i in range(2, a):
        check = 0
        for j in range(1, i + 1):
            if i % j == 0:
                check += 1
            if j == i and check == 2:
                list.append(i)
               
    return list


a = int(input())
primeNumList = []

for _ in range(a):
    primeNumList.append(int(input()))
    
for num in primeNumList:
    if num % 2:
        continue
    tempList = PrimeNumber(num)
    resultList = []
    
    for i in range(len(tempList)):
        if i == len(tempList) - 1:
            break
        for j in range(len(tempList)):
            if tempList[i] + tempList[j] == num:
                resultList.append((tempList[i], tempList[j]))
                break
    
    a, b = resultList[0][0], resultList[0][1]
    for i in resultList:
        if abs(a - b) > abs(i[0] - i[1]):
            a, b = i[0], i[1]
           
    if a > b:
            print(f'{b} {a}')
    else:
        print(f'{a} {b}')

어마무시 함.... 당연히 beakjoon에서 시간 초과 남.

다른 방법으로

1. 소수를 판별하는 함수를 만든다.
2. input값을 반으로 쪼갠 후, 두 변수에 넣어준다.
3. 두개의 변수가 소수면 출력, 아니면 하나의 변수는 1빼주고, 다른 하나는 1 더해준 후
4. 다시 for문을 돌린다.

그래서 나온 코드

def PrimeNumberCheck(a):
    check = 0
    
    if a == 2:
       return True
   
    for i in range(1, a + 1):
        if a % i == 0:
            check += 1
        if i == a and check > 2:
            return False
        
    return True


a = int(input())

for _ in range(a):
   num = (int(input()))
   
    elementA = num // 2
    elementB = num // 2
    
    for _ in range(num // 2):
        if PrimeNumberCheck(elementA) and PrimeNumberCheck(elementB):
            print(elementA, elementB)
            break
        
        else:
            elementA -= 1
            elementB += 1

괜찮았다고 생각했는데 이것도 시간초과나옴.... 분함...
그래서 잠시 쉴겸 재귀함수 알고리즘 보고 있는데 이 것도 어려워서 머리 깨지는 중...
내일 저거 풀고 재귀함수 다시 봐야겠다