본문 바로가기
728x90

수학33

[python] 백준 17471 게리맨더링 https://www.acmicpc.net/problem/17471 17471번: 게리맨더링 선거구를 [1, 4], [2, 3, 5, 6]으로 나누면 각 선거구의 인구는 9, 8이 된다. 인구 차이는 1이고, 이 값보다 더 작은 값으로 선거구를 나눌 수는 없다. www.acmicpc.net 문제 해결 삼성 A형 기출문제 딱 봐도 완전탐색 문제이다.(2 ≤ N ≤ 10, 1 ≤ 구역의 인구 수 ≤ 100) 문제는 combination을 사용하여 모든 경우의 수를 다 고민을 해야하나인데... 맞다. 1개부터 n//2 개까지 선거구를 뽑은 다음 다 연결 되었는지 확인하고 나머지 선거구끼리도 모두 연결되었는지 확인해야한다. 모두 연결이 되면 두 집단의 인구 차이를 이전과 비교해서 작은 값을 저장한다. 삼성은 i.. 2023. 4. 26.
[python] 백준 1788 피보나치 수의 확장 https://www.acmicpc.net/problem/1788 1788번: 피보나치 수의 확장 첫째 줄에 F(n)이 양수이면 1, 0이면 0, 음수이면 -1을 출력한다. 둘째 줄에는 F(n)의 절댓값을 출력한다. 이 수가 충분히 커질 수 있으므로, 절댓값을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 문제해결 |n| >1 일 때 F[n] = F[n-1] + F[n-2] 를 이용해서 새로운 수를 F 리스트에 넣는다. n을 음수로 확장시켰으 때 놀라운 규칙을 알면 끝이다. CODE n = int(input()) s = [0, 1] for i in range(2, abs(n) + 1): s.append((s[i - 1] + s[i - 2]) % 1000000000) i.. 2023. 4. 17.
[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.
728x90