20210808 TIL

백준 단계별로 풀어보기 9단계 중 예제 6~7단계 작성하기

9020번, 1085번 문제를 풀고 다음 글에 해당 내용을 업데이트했다.
[9단계] 파이썬3으로 백준 단계별로 풀어보기- 기본 수학 2

예제 6단계 문제도 에라토스테네스의 체를 이용했다.
초반에 작성한 코드가 ‘시간 초과’ 결과가 나와서, 시행착오를 거쳤다.
초반에 작성한 코드는…
먼저 n 이하의 소수를 리스트 자료형으로 반환하는 함수를 정의한다.
테스트 케이스의 개수를 입력받고,
각 테스트 케이스에 대해 n을 입력받은 다음 앞서 정의한 함수로 n 이하의 모든 소수를 구하고,
모든 소수를 for문으로 확인하여, n//2 이하일 경우, 그 중 (n-소수)가 소수에 해당할 경우 (소수, n-소수)를 출력한다.

백준에 제출했더니 ‘시간 초과’가 나왔다.

input()을 sys.stdin.readline()으로 바꿔보기도 하고(<- 반복문으로 여러 줄 입력 받을 때 input()은 비교적 오래 걸려서 시간 초과 나올 수 있다고 함. 백준 15552번_단계별로 풀어보기 3단계 중 예제 4번)
math.sqrt()를 ** 연산자로 바꿔보기도 하고(<- 바꿔도 ‘시간 초과’, 큰 차이 없는 것인가?)

그래도 ‘시간 초과’가 나왔다.

이번에는 코드 내용을 바꿔봤다.
n이 4 이상 10000 이하의 짝수라고 문제에서 범위를 제한했는데.. 이는 상대적으로 작은 수라고 생각했고,
n을 입력받을 때마다 n 이하의 소수를 구하는 것보다
10000 이하의 소수를 미리 구해두고, n을 입력받으면 원하는 범위의 숫자를 찾는 게 더 빠르리라 생각했다.

따라서 n 이하의 소수를 구하는 함수를 정의하지 않고, 10000 이하의 소수를 구하여 리스트로 저장했다.
테스트 케이스의 개수를 입력받고
각 테스트 케이스에 대해 n을 입력받은 다음,
for문으로 j를 n//2부터 1씩 감소하며 확인하는데, j가 소수에 해당하고, n-j도 소수에 해당하는 j를 찾아내서 (j, n-j)를 출력한다.

성공했다! 메모리 29200KB, 시간 1856ms

예제 7단계 문제는 비교적 간단한 기하학 문제였다.
직사각형 내부 좌표(x, y)에서 직사각형의 경계선으로 가는 최단 거리를 출력하는 문제이다.
직사각형은 각 변이 좌표축과 평행하므로 내부 좌표에서 경계선까지 가는 최단 거리는 좌표(x, y)와 경계선(x = 0, x = w, y = 0, y = h) 사이의 |x축 좌표 차이|, 또는 |y축 좌표 차이| 로 나타낼 수 있었다.
좌표(x, y)에서 모든 경계선까지의 거리를 구하고, 이 중 최솟값을 출력하면 된다.

GitHub에 올린 소스 코드는 아래에 있다.
level6-9020-골드바흐의추측.py
level7-1085-직사각형에서탈출.py