탐색 범위를 줄여야하는 브루트포스 연습4 - 평면 위에 직사각형 쳐서 점 고르기

2187번: 점 고르기 평면 위 n개의 점이 있는데, 세로로 A, 가로로 B인 직사각형을 쳐서 이 안에 있는 점의 크기의 최댓값과 최솟값의 차이가  가장 크게 직사각형을 만들고 싶다 보면 N  그러다보니 직사각형의 크기를 1부터 2*10^6까지 돌리고 직사각형 위치를 2*10^6*2*10^6... 해보면.. 당연히 시간초과 그런데 구하고자 하는 것이 직사각형 크기 이런건 아니고 아무 직사각형이나 쳐서 그 안에 점 크기의 최댓값 - 최솟값의 차이를 최대로 만드는거 어떤 점들이 들어오느냐 이게 중요 그래서 점 i를 기준으로 잡아서 점 j를 순회해서 크기가 A*B인 직사각형을 만들 수 있는지 고려해보고  가능하다면 두 점 i,j는 직사각형 내부에 있기 때문에 두 점 i,j의 크기를 최댓값, 최솟값으로 갱신해서..

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

탐색 범위를 줄여야하는 브루트포스 연습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

탐색 범위를 줄여야하는 브루트포스 연습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