문제 링크
로그인을 해야만 볼 수 있다.
문제 해결
1. K번 째 극단적인 수를 구하는 문제. K의 범위가 10억이므로 자료구조에 담아서 해결하기에 부적합.
2. 극단적인 수를 길이로 나눠보면 길이가 1 늘어날 때, 2배씩 늘어남을 알 수 있다. 이를 이용해서 K번 째 극단적인 수의 길이를 먼저 구한다.
3. K번 째 극단적인 수의 길이가 L이라고 하자. 44...44 부터 77....77 까지는 부터 번 째라고 할 수 있다.
4. 같은 길이의 극단적인 수를 오름차순으로 정렬하면, 맨 앞자리 부터 절반씩 4 또는 7로 나뉘게된다. 그러므로 이분탐색을 이용해서 mid 보다 작으면 4를 출력하고 아니면 7을 출력한다.
주의할 점 || 생각해볼 점
1. 이분탐색을 할 때 끝점을 으로 설정하고, (시작점+1) < (끝점) 을 조건으로 삼는다.
참고
-
※ 정확하고 부드러운 태클은 언제나 환영입니다.
'Problem Solving > 파라메트릭 & 이분 탐색' 카테고리의 다른 글
BOJ 1166 - 선물 (1) | 2017.07.12 |
---|---|
BOJ 1072 - 게임 (0) | 2017.05.19 |