본문 바로가기

백준다이아2

백준 13705, Ax+Bsin(x)=C 개요 문제 링크 다이아 5, 임의정밀도/큰 수 연산 Ax+Bsin(x)=C를 만족하는 x를 임의 정밀도를 고려해 구하기 접근 이분탐색을 사용하는 문제라고하면 두 가지 유형이 있는데, 하나는 실행 횟수를 줄이기 위한 문제이고 하나는 오차를 완벽히 구할 수 없는 문제이다. 이 문제는 후자에 속하는데, sin(x)의 오차가 문제가 원하는 수준의 오차보다 크게 발생한다. 이분탐색이면 왼쪽과 오른쪽을 잘 설정해야 하는데, Ax=C로 가정하고 구해도 되지만, sin의 범위는 -1부터 1까지라서 다음의 부등식이 성립한다. -B c; LF A,B,C,l,r,x; A=a,B=b,C=c; LF U=1000000, D=0.5; l = (C-B)/A; r = (C+B)/A; int t=80; while(t--) { x = (.. 2023. 3. 14.
백준 13165, 이것도 해결해 보시지 개요 문제 링크 다이아 5, 선형대수학, 무작위화 A×B=C를 만족하는 겹치지 않는 부분행렬의 최대개수 접근 Freivald's algorithm을 사용하는 세 문제 중 두 번째. 다이아 하위 문제는 보통 새로운 어려운 알고리즘을 사용하는 문제가 많은 것 같다. 그래봐야 전체 2700개 다이아 문제 중 7개 풀었지만 내 좁은 시야에서는 암튼 그렇다. 문제로 돌아오자. 우선 정수범위가 터질 수 있으니 long long을 사용하고, N이 256이고, L이 4000에서 100만정도 되므로 시간을 잘 관리해야 한다. O(N^3)에 하면 무조건 터지므로 O(kN^2)에 A×B=C를 유사하게 검증할 수 있는 프리발즈 알고리즘을 사용한다. 다음으로 0부터 L까지 돌면서 개수를 세어주면 되는데, 앞에서부터 그냥.. 2023. 3. 13.

티스토리툴바