https://www.acmicpc.net/problem/1300
문제 설명
문제
세준이는 크기가 N×N인 배열 A를 만들었다. 배열에 들어있는 수 A[i][j] = i×j 이다. 이 수를 일차원 배열 B에 넣으면 B의 크기는 N×N이 된다. B를 오름차순 정렬했을 때, B[k]를 구해보자.
배열 A와 B의 인덱스는 1부터 시작한다.
입력
첫째 줄에 배열의 크기 N이 주어진다. N은 105보다 작거나 같은 자연수이다. 둘째 줄에 k가 주어진다. k는 min(109, N2)보다 작거나 같은 자연수이다.
출력
B[k]를 출력한다.
- 풀이 -
이 문제는 웰노운 이분탐색이다.
차례대로 설명해보자.
1. 일단 N과 K를 입력 받는다.
그리고 cnt,sNum,l,r 변수를 초기화 해주자.
sNum을 이분 탐색을 위한 초기 작은 수로 K의 절반으로 정해주자.
그러면 l을 1로 r을 k로 초기화 해준다.
이제 l과 r로 이분 탐색을 수행해주자.
단계 마다 sNum은 l이랑 r의 중간 값으로 설정을 계속한다.
이제 이 과정을 l과 r이 같아질 때까지 반복한다.
최종적으로 l과 r이 같아지면 sNum이 원하는 조건을 만족하는 최소값이 될거다.
그럼 이 sNum을 출력하면 끝이다. 참 쉽죠?
우리 킹갓 제네럴 ps 마이너 갤러리 이용자 분들은 쉽게 푸실거 같지만 혹시만 써봤습니다 감사합니다
뎃?
문제만 보고 호다닥 달려가서 풀었는데 존나 오래걸렷네