N
BOJ-1002 (Silver IV)
케이스만 꼼꼼히 나누면 되는 문제였다. # 부동소수점에 주의한다. sqrt()사용주의 T = int(input()) answer = 0 for _ in range(T): x1,y1,r1,x2,y2,r2 = map(int, input().split()) #case1: 두원이 멀리떨어져 접하지 않을때: return 0 if (x2-x1)**2 + (y2-y1)**2 > (r1 + r2)**2: answer = 0 #case2: 두원이 겹칠때: return -1 elif (r1==r2 and x1==x2 and y1==y2): answer = -1 #case3: 두원이 외접할때: return 1 elif (r1+r2)**2 == (x2-x1)**2 + (y2-y1)**2: answer = 1 #case4: 두..
BOJ-9020 (Silver I)
소수판별 문제에서의 핵심은 기본적으로 소수판별횟수를 얼마나 줄일수 있냐인것같다. 우선 n이 제한된 이상 앞선 4948번의 베르트랑 공준 문제에서 해결한 것 처럼 미리 범위내 소수를 모두 리스트업 해둔 후에 계산하는 것이 효율적일 것 같다. 그 후 n을 이루는 두개의 소수, 골드바흐 파티션을 찾아내는 방법에 여러가지가 있을 것 같은데 생각나는 가장 간단할 것 같은 방법은 리스트 요소를 [0] 부터 n에서 빼가면서 뺀 나머지가 소수인지(리스트안에 들었는지)를 판별하는 것이다. 그렇게 해서 둘다 소수라면 출력한다. import sys def is_prime(x): if x==1: return False sq = int(x**0.5) for i in range(2, sq+1): if x%i==0: return ..
BOJ-4948 (Silver II)
https://www.acmicpc.net/problem/1929 에서 풀었던대로 하면 똑같이 시간제한 안에 해결될 것이라 생각했는데 시간이 초과되었다. 이를 해결하기 위해 문제에서 제시한 제한사항을 고려하기로 했다. 이전 방식은 인풋이 들어올때마다 범위내 소수를 계산했는데 이러면 소수를 여러번 반복해서 구하게된다. 이것을 방지하기 위해서 제한범위인 1~123456*2 이내의 모든 소수를 구해 리스트업하고 그 리스트와 대조하면 반복을 없앨 수 있다. import sys def is_prime(x): if x==1: return False sq = int(x**0.5) for i in range(2, sq+1): if x%i==0: return False return True # 값들어올때마다 반복하지 말..
BOJ-1929 (Silver II)
1~판별할 수의 제곱근까지만을 체크해도 작동한다. 이렇게 하면 시간내로 통과가 가능하다. 입력시간도 sys.stdin.readline() 을 input()대신 사용해 줄일 수 있다 import sys def is_prime(x): # M부터 N-1의 수로 나눠서 if x==1: return False sq = int(x**0.5) for i in range(2, sq+1): if x%i==0: return False return True M, N = map(int, sys.stdin.readline().split()) for i in range(M,N+1): if is_prime(i): print(i)