탐색 범위를 줄여야하는 브루트포스 연습3 - 해밍 수열의 i번째 수 찾기

7868번: 해밍 수열 3개의 소인수 p1,p2,p3이 주어질 때 p1,p2,p3만으로 소인수를 가지는 자연수의 오름차순 배열에서 i번째 수를 찾는 문제 H(2,3,5)는 2,3,4,5,6,8,9,10,12,...  p1,p2,p3,i가 10^18보다 작다고 하니까 단순하게 다 돌려보는건 어려울것 같고 p1,p2,p3만을 소인수로 가지니까 H(p1,p2,p3)는 $p1^{n1} * p2^{n2} * p3^{n3}$ 여기서 출력하는 수가 10^18보다 작다고 하니까 결국 $p1^{n1} * p2^{n2} * p3^{n3}$도 10^18보다 작아야함 따라서 n1,n2,n3  따라서 p1,p2,p3가 주어질때 0~59 * 0~59 * 0~59로 3중 for문 돌아보면서  p1**n1 * p2 ** n2 * p..

• format_list_bulleted 브루트포스
• · 2024. 11. 11.
• textsms

숨어있는 기준을 찾는 브루트포스1 - 수많은 좌표들을 얼마나 평행이동해야 일치하는가

5588번: 별자리 찾기 좌표 집합 A와 B가 주어질때 A를 얼마나 평행이동 시켜야 B의 부분집합이 될 수 있는가? 아래의 경우 2,-3 이동시키면 B의 빨간 부분과 일치시킬 수 있다   A의 별 개수 m이 최대 200개이고 B의 별 개수 n이 최대 1000개 x,y값은 최대 10^6까지...  그러면 200개 * 1000개 돌아보면서... 평행이동 시킬 수 있는 양 10^6까지 하나하나 돌아봐야하나?? 그런데 A의 모든 점은 서로 동일하게 (dx,dy)만큼 이동한다는 점 +  B의 점들 집합의 일부가 되어야하므로, A의 한 점이 B의 모든 점 각각에 대하여 얼마만큼 이동해야 가능한지  (dx,dy)를 모두 구해놓는다면?    가능한 (dx,dy) 후보는 최대 1000개이고 각각에 대해서 A의 모든 점에..

• format_list_bulleted 브루트포스
• · 2024. 11. 9.
• textsms

브루트포스 문제 복기하면서 실수한 부분 체크하기1(어디서든 시작할 수 있다)

3129번: 상범이의 은밀한 메세지 암호화된 메시지랑 원본 메시지의 일부가 주어질떄, 원본 메시지를 찾는 문제 각 메시지에서 알파벳을 0~25로 치환하고  원래 메시지 + 키 = 암호화된 메시지 이기 때문에 암호화된 메시지 - 원래 메시지 = 키임을 알 수 있다. 여기서 원래 메시지의 일부분만 보여지기 때문에 암호화된 메시지랑 원래 메시지를 비교해서 가능한 모든 키를 구해야한다. 예를 들어 암호화된 psinottfn과 원래 메시지 most가 주어지는데 원래 메시지 most는 어디 부분인지 모르니까 0번부터 5번까지 most를 비교해보면서 키를 찾는다 psinottfnmost psinottfn  most ... for i in range(len(a)-len(b)+1): K = [] for..

• format_list_bulleted 브루트포스
• · 2024. 10. 26.
• textsms

탐색 범위를 줄여야하는 브루트포스 연습2 - 컴퓨터로 종이접기?

12979번: 종이 접기  종이의 크기 W,H인 종이가 주어질때 종이를 적절히 접어서 넓이가 A가 되도록 만들고 싶다. 종이를 접더라도 직사각형이 되도록 접어야하고 접고 나서도 W,H는 항상 정수가 되어야한다. 여기서 W,H가 10^9까지인데 A가 10^5까지라는 점에 주목하자. W,H로 뭔가 해보는건 어려울것 같지만 적어도 A는 1~10^5까지 다 돌아볼만하다. X*Y = A가 될려면 당연히 X,Y는 A이하여야한다. 그래서 A를 기준으로 1~A까지 돌아서 그 값을 X라고 둔다면, Y는? A가 X로 나누어 떨어질때, Y = A//X가 된다. 이러한 X,Y를 찾았다면 주어진 W,H에서 찾은 X,Y로 몇번만에 이동할 수 있는지 체크하면 된다.  W에서 X로 갈려면 가장 빠르게 갈려면 몇번만에 갈수 있을까? ..

• format_list_bulleted 브루트포스
• · 2024. 10. 25.
• textsms

탐색 범위를 줄여야하는 브루트포스 연습1 - 각 자릿수의 제곱합?

17755번: Równanie 정수 k가 주어질때 a  여기서 f(n)은 n을 10진법으로 표현했을 때 각 자릿수의 제곱합 k,a,b  이럴때는 탐색범위를 좁힐 수 있는지 생각해봐야한다  f(n)이 n을 10진법으로 표현했을 때 각 자릿수의 제곱합이므로,  $n = a_{1} * 10^{x_{1}} + a_{2} * 10^{x_{2}} + a_{3} * 10^{x_{3}} + ...$이므로  $f(n) = a_{1}^{2} + a_{2}^{2} + ....$인데 여기서 $a_{i}  그런데 n이 최대 10^18이므로 f(n)이 최대가 될려면 999999999999999999로 9가 18개 있는경우이다. 이 경우 81*18 = 1458이라서 f(n)으로 가능한 값은 1부터 1458까지이다.  그러므로 ..

• format_list_bulleted 브루트포스
• · 2024. 10. 24.
• textsms

나눗셈 실수오차가 생긴다면 직접 나눗셈을 구현하기

1206번: 사람의 수 (acmicpc.net)  n명의 사람이 0점부터 10점까지 정수로 존재하는 설문조사 문항에 점수를 내서 각 문항마다 평균을 낸 점수가 실수로 주어질때, n이 될 수 있는 가장 작은 정수를 구하는 문제 평균이 소수점 셋째자리까지만 주어진다 예를 들어 32/106 = 0.3018867924528302... 인데 0.301만 주어지는 ---------------------------------------------------------------------------------------------------------------------------------- 만약 설문조사한 사람 수가 x명이고 i번째 문항의 점수 합이 v이면  $$\frac{v}{x} \approx A[i]$$  A..

• format_list_bulleted 정수론
• · 2024. 9. 26.
• textsms