21676번: Газон (acmicpc.net) 왼쪽 아래 (x1,y1), 오른쪽 위 (x2,y2)로 주어지는 사각형과 중심 (x3,y3), 반지름 r로 주어지는 원이 서로 겹치는 영역의 정수 점 (x,y)의 개수를 구하는 문제 정말 단순하게 생각하면 사각형 안의 모든 정수 점 (x,y)에 대하여 원의 방정식 내부 (x-x3)**2 + (y-y3)**2 def check(x,y): v = (x-x3)**2 + (y-y3)**2 if v 하지만 x1,x2,y1,y2,x3,y3의 범위가 -10만~10만이라 $O(N^{2})$은 시간초과가 날수밖에 없다 하지만... 이것말고 방법이 있나? x를 정했으면 그거에 대해 y는 모든 범위를 돌아봐야할텐데..? 방법은 원의 방정식은 (x-x3)..
1. 어떻게 남녀를 맺어줘야 행복하게 살수 있을까? 결혼중매업자인 대혁에게는 200명의 고객이 있다. 100명은 남자, 100명은 여자이다. 여자 고객은 각자 남자 고객 100명을 대상으로 선호도에 따라 순위를 매겨 대혁에게 제출한다. 각자 명단의 맨 위에는 완벽한 이상형이 있고, 아래로 갈수록 호감도가 떨어져 맨 아래에는 최악의 기피남이 있다. 남자 고객 100명도 마찬가지로 여자 고객 100명을 대상으로 순위를 매겨 제출한다 대혁은 이 선호도 조사 결과를 바탕으로 남녀 고객을 맺어줘야한다. 어떻게 맺어줘야 이들이 결혼에 골인하고 가정을 이루고 오래오래 행복하게 살 수 있을까? 당연한 말이지만, 일부는 자신의 제1지망과 맺어지지 못한다. 같은 남자를 여러 여자가 제1지망으로 찍었다면 누군가는 고배를 ..
20744번: Cucumber Conundrum (acmicpc.net) 반지름이 s인 원 모양의 샌드위치가 있고 반지름이 r인 원 모양의 피클이 n개 있는데 이 피클을 샌드위치 위에 최대한 많이 높고 싶다 이 때 샌드위치 면적의 최대 z%까지만 놓을 수 있고 두 피클이 서로 겹치지 않아야한다 최대 몇개의 피클을 놓을 수 있는가? 샌드위치의 면적이 $\pi * s^{2}$이고 이것의 최대 z%가 피클 x개의 넓이 $\pi * r^{2} * x$이므로 $$\pi * s^{2} * \frac{z}{100} >= \pi * r^{2} *x $$ 식을 정리하면 $x 사실 이것만 만족하면 되는줄 알았는데... 아니더라고 https://en.wikipedia.org/wiki/Circle_packing_in_a_..
29313번: Стадион (acmicpc.net) 일렬로 된 N개의 좌석이 있는데 사람이 양쪽으로 들어가서 좌석에 앉을 수 있다고 할때, 어떤 사람이 이미 앉은 사람을 지나치지 않고 N명이 모두 앉는 방법의 수를 구하는 문제 예를 들어 3명이 앉는다고 해보면 이렇게 4가지가 있다 N개의 자리가 있을 때 _ _ _ _ _ _ ... 첫번째 자리에 먼저 앉으면 1 _ _ _ _ _ ... 나머지 N-1개의 자리는 고정적으로 2,3,4,5,6,... 으로 1가지 = N-1C0가지 결정된다 두번째 자리에 먼저 앉으면 _ 1 _ _ _ _ .... 1의 왼쪽 자리 _ 를 N-1명중 1명을 결정시키면 1의 오른쪽은 무조건 자동으로 결정되므로... N-1C1가지 왜냐하면 1의 왼쪽에 3을 앉히면 3 1 ..
28828번: Упражнения в умножении (acmicpc.net) $\frac{a_{1}a_{2}...a_{n}}{b_{1}b_{2}...b_{m}}$과 $10^{6}$ 이하로 차이나는 정수를 구하는 문제 n,m이 $10^{5}$까지이고, $a_{i}, b_{i}$가 $10^{9}$이라 단순하게 곱하고 나누면 시간초과가 난다 v1 = 1for i in range(n): v1 *= A[i]v2 = 1for j in range(m): v2 *= B[j]print(v1//v2) 곱셈을 덧셈으로 바꾸는 대표적인 방법이 로그를 취하는 것이다 $\frac{a_{1}a_{2}...a_{n}}{b_{1}b_{2}...b_{m}} = X$라고 하면 $$logX = log(a_{..
14108번: Umnozak (acmicpc.net) n자리 자연수중에서 짝수 위치의 자리수들의 곱과 홀수 위치의 자리수들의 곱이 서로 같게되는 그러한 자연수들의 개수를 구하는 문제 첫번째 자리는 홀수 위치라고 가정 1자리 자연수는 홀수 위치밖에 없으니 0개 2자리 자연수는? 11,22,33,44,55,66,77,88,99로 9개 3자리 자연수는? 100부터 999까지 전수조사해보는게 나을 것 같다 count = 0for i in range(100,1000): s = str(i) a = 1 b = 1 for j in range(len(s)): if j % 2 == 0: a *= int(s[j])..
딥러닝/머신러닝, 통계학, IT프로그래밍, 알고리즘을 좋아하는 사람 https://github.com/yundaehyuck
