[D3] SWEA 16002. 합성수 방정식

1. 접근 방식

1 <= N <= 10^7

2 <= x,y <= 10^9

 

조건이 정말 커서,

어떠한 뻥 뚫리는 해법이 없을까?

고민했다.

하지만, 찾지 못했고

2<=x,y<=10^9의 조건에 해당 하는 수를 

모두 탐색해 합성수인지 아닌지 판단하고

+n,-n에 해당하는 수가 합성수인지 아닌지 판단할려했다.

근본적으로 잘못된 풀이인게, 조건이 어마어마하게 크다.

제곱근으로 어떻게 커버할 수 있을거라 생각한게 잘 못이다.

 

2가지의 풀이가 있다.

(1).나의 정석적인 풀이에 야매가 섞인 건데

(2,10^9)까지의 범위에서 탐색을 해주다가

합성수와 그 합성수보다 n이 큰 합성수가 발견되면

값들을 출력해준 뒤, 반복문은 더 이상 탐색하지않는다.

어찌 되었든, pass는 됐는데 영 찜찜한 풀이다.

하지만, 시험장에서 어찌되었든, 문제 풀이만 

통과하면 되기에 이 방법이라도 생각해내야한다.

 

(2).(x+1) * (n) - (x) * (n) = n

ex) 9*n-8*n=n

이 풀이를 보고, 정말 허를 찌르는 듯한 느낌을 받았다.

왜 이 사실을 유추해내지 못했을까??

합성수에 어떤 값을 곱해도 어찌 되었든 합성수일테고...

결과적으로 후자가, 이 문제에 적합한 풀이라 생각한다.

 

2. 디테일한 구현

어떠한 수가 무슨 수의 곱으로 이루어져있는지

탐색할 때 1부터 그 수 까지 탐색할 필요 없고

제곱근까지 탐색해주면 된다.

이것은 시간 단축에 도움을 주는 팁이다. 

 

3. 코드 구현

def num_check(s): ##어떤 수 s가 합성수 인지 아닌 지 판단해주는 함수
        for i in range(2,int(s**0.5)+1):
            if s%i==0:
                return True
        return False
            
   
 
if __name__=='__main__':
  #  sys.stdin=open('input2.txt','r')   
    
    
    t=int(input()) ## 총 테스트 케이스 개수
    
    for tc in range(t):
        n=int(input())
        odd_num=[] ##합성수들 모음
        for i in range(2,10**9):
           if num_check(i) and num_check(i+n):
               print(f'#{tc+1} {i+n} {i}')
               break

 

if __name__=='__main__':
    #sys.stdin=open('input2.txt','r')   
    
    
    t=int(input()) ## 총 테스트 케이스 개수
    
    for tc in range(t):
        n=int(input())
        print(f'#{tc+1} {9*n} {8*n}')

4. 깨달은 점 및 반성

야매로라도 풀어봐야한다.

천천히 풀이법을 잘 생각해보자