Problem Solving/파라메트릭 & 이분 탐색 썸네일형 리스트형 BOJ 1166 - 선물 문제 링크https://www.acmicpc.net/problem/1166 문제 해결 1. 기본적인 파라메트릭 서치를 이용한 문제다. 주의할 점 || 생각해볼 점 1. solve 함수를 구현할 때, 무작정 주어진 L, W, H를 곱해서 해결하면 안된다. 각 변수 당 최대 이기 때문이다. 2. while(right-left>1e-10) 를 사용하는 것에 조심하자. 경우에 따라선 right-left가 항상 1e-10일 수 있다. 3. 16 byte를 표현할 수 있는 long double 을 사용했다. 이번 문제에선 8 byte를 표현할 수 있는 double을 사용하지 않는다. 참고 ※ 정확하고 부드러운 태클은 언제나 환영입니다. 더보기 codeground practice - 극단적인 수 문제 링크 로그인을 해야만 볼 수 있다. 문제 해결 1. K번 째 극단적인 수를 구하는 문제. K의 범위가 10억이므로 자료구조에 담아서 해결하기에 부적합. 2. 극단적인 수를 길이로 나눠보면 길이가 1 늘어날 때, 2배씩 늘어남을 알 수 있다. 이를 이용해서 K번 째 극단적인 수의 길이를 먼저 구한다. 3. K번 째 극단적인 수의 길이가 L이라고 하자. 44...44 부터 77....77 까지는 부터 번 째라고 할 수 있다. 4. 같은 길이의 극단적인 수를 오름차순으로 정렬하면, 맨 앞자리 부터 절반씩 4 또는 7로 나뉘게된다. 그러므로 이분탐색을 이용해서 mid 보다 작으면 4를 출력하고 아니면 7을 출력한다. 주의할 점 || 생각해볼 점 1. 이분탐색을 할 때 끝점을 으로 설정하고, (시작점+1) .. 더보기 BOJ 1072 - 게임 문제 링크https://www.acmicpc.net/problem/1072 문제 해결 1. 처음 주어진 게임 수와 승리 수를 토대로 승률 (winning_rate)을 구한다. 2. 앞으로 치뤄야 할 경기의 수를 Parametric Search로 구한다. 주의할 점 || 생각해볼 점 1. 앞으로 계속 이길 예정이므로 게임을 치루게되면 승률은 99~100% 사이가 된다. 이미 승률이 99% 이상이면 더 이상 오를 승률이 없게된다. 이 때 문제에서 요구한대로 ' -1 ' 을 출력한다. 참고 - ※ 정확하고 부드러운 태클은 언제나 환영입니다. 더보기 이전 1 다음
