728x90 정수론13 [python] 백준 5615 아파트 임대 https://www.acmicpc.net/problem/5615 5615번: 아파트 임대 첫째 줄에 아파트의 면적의 수 N이 주어진다. 다음 줄부터 N개 줄에 카탈로그에 적혀있는 순서대로 면적이 주어진다. N은 100,000이하이고 면적은 231-1이하인 양의 정수이다. www.acmicpc.net 문제해결 2xy+x+y로 무엇을 할 수 있을지 생각하면 아무것도 할 수 없다.(1차 고비) 인수분해를 해야할 것 같은데 S = 2xy+x+y라 할 때 2S+1 = (2x+1)(2y+1)로 인수분해 할 수 있다. 2S+1은 두 홀 수의 곱으로 나타낼 수 있는 것이다. 그럼 이것을 왜 하는 것인가? 바로 2S+1이 소수인지 판별해서 S를 판별하면 되는 것이다. 2S+1이 소수인지 판별하는 것은 밀러-라빈 소수 .. 2023. 7. 31. [python] 백준 15711 환상의 짝궁 https://www.acmicpc.net/problem/15711 15711번: 환상의 짝꿍 환상의 나라 디디랜드에서는 인연의 증표로 끈을 하나씩 가지고 있다. 그들은 지극히 평범한 방법으로 이 끈을 이용하여 어떤 두 사람이 환상의 짝꿍인지 판단하는데, 두 사람의 끈을 서로 이 www.acmicpc.net 문제 해결 시간과 메모리 모두 빡빡한 문제이다. A, B 가능한 숫자가 $10^{12}$를 넘어가기 때문에 줄여서 계산해야한다. 골드바흐의 추측 (2보다 큰 짝수는 두 소수의 합으로 나타낼 수 있다.)를 생각해야한다.(2이면 1+1이므로 "NO"출력 2보다 큰 짝수는 "YES"출력 하면 된다. 3은 'NO'임을 알 수 있고 5이상의 홀수 x 는 x= 2 + (x-2)로 나타낼 수 있다. x-2가 소수.. 2023. 4. 4. [python] 백준 2485 가로수 https://www.acmicpc.net/problem/2485 2485번: 가로수 첫째 줄에는 이미 심어져 있는 가로수의 수를 나타내는 하나의 정수 N이 주어진다(3 ≤ N ≤ 100,000). 둘째 줄부터 N개의 줄에는 각 줄마다 심어져 있는 가로수의 위치가 양의 정수로 주어지며, 가 www.acmicpc.net 문제 해결 각 나무 사이의 거리를 모아서 최대 공약수를 구한다. 최대 공약수를 나무와 나무 사이 거리로 생각하여 나무에서 최대 공약수만큼 떨어진 곳에 나무가 없으면 나무를 세우면 된다. CODE import sys input = sys.stdin.readline import math n = int(input()) a = int(input()) # 첫 번째 나무 좌표 A = [] for i .. 2023. 3. 30. [python] 백준 9506 약수들의 합 https://www.acmicpc.net/problem/9506 9506번: 약수들의 합 어떤 숫자 n이 자신을 제외한 모든 약수들의 합과 같으면, 그 수를 완전수라고 한다. 예를 들어 6은 6 = 1 + 2 + 3 으로 완전수이다. n이 완전수인지 아닌지 판단해주는 프로그램을 작성하라. www.acmicpc.net 문제 해결 완전수의 가장 클 수 있는 약수는 n%2==0일 때 n//2 따라서 1부터 n//2+1까지 for문을 통해 나눠 떨어지는 수를 찾는다. 더해서 n이 나오면 완전수이다. 표현은 n,=은 각각 sep=' '로 출력하고 ' + '.join을 통해 더하기를 표현할 수 있다. 아니면 N is NOT perfect. 나오도록 출력 CODE import sys input = sys.stdin.. 2023. 3. 16. 이전 1 2 3 4 다음 728x90