코딩하기 좋은날
백준 1300 K번째 수 본문
https://www.acmicpc.net/problem/1300
문제와 채점은 위 사이트에서 확인 하실 수 있습니다
이 문제는 N*N배열이 있을 때 이 배열엔 i*j의 숫자가 들어있다고 하고 이 배열을 일차원 배열에 오름 차순으로 정렬 할때 K번째 수를 구하는 문제입니다.
처음에 분류가 이분탐색으로 되어 있어서 그렇게 생각하고 봤는데도 접근을 잘 못하겠어서 다른 글들을 참고하였습니다.
우선 배열에 i*j의 숫자들이 저장 되어 있으므로 K보다 작은 숫자의 개수를 찾고 싶다면 K/i를 해야 구할 수 있다는 것이 포인트입니다.
문제의 예시를 보면 N이 3이고 K가 7일때를 예로 들고 있습니다. 이경우
3*3 배열이므로 아래와 같이 수가 있고 예를 들어 7보다 작은 숫자의 개수를 찾고 싶다면 7/1 + 7/2 + 7/3 을 하는데 이때 7/1 같은경우 7이라는 숫자가 나옵니다. 따라서 몫이 N보다 큰경우는 그 개수가 N개인것과 동일하므로 min(K/i, N) 이라는 식을 사용해야 하는 것을 알 수 있습니다.
1 2 3
2 4 6
3 6 9
자 그렇다면 이제 여기에 이분탐색을 적용시켜 시작 위치를 1로 끝 위치를 K로 하여서 진행을 해주면 됩니다.
위의 예시로 진행과정을 보면 start = 1 end = 7 이므로 mid 지점은 4가 됩니다.
따라서 총 개수는 3+2+1로 6개 입니다. K가 7이므로 start를 mid+1인 5로 바꿔줍니다.
2번째 과정에서 mid는 6이므로 6을 대상으로 계산을하면 3+3+2 = 8개가 나옵니다.
이제 8은 K보다 크므로 result에 mid값을 넣어주고 end에 mid-1을 넣어줍니다.
3번째 과정은 start = 5 end = 5 이므로 mid가 5가나옵니다. 이때 총 개수는 3+2+1 = 6개입니다.
start와 end가 동일하므로 마지막 과정이고 5보다 작은수는 6개이고 6보다 작은수는 8개이므로 7번째 수는 6이라는 것이 나오게 됩니다.
처음에 이해가 잘 안되었는데 이렇게 직접 예시를 들어서 생각하면 이해가 잘 되는 것 같습니다. 이분탐색 문제는 이 문제가 이분탐색으로 푸는게 맞는가 를 생각하는것이 어려운 것 같습니다.
다음은 코드입니다.
#include <iostream>
using namespace std;
int main(void) {
ios_base::sync_with_stdio(false); cin.tie(NULL);
int N,k;
cin >> N >> k;
int start = 1;
int end = k;
int result = 0;
while(start <= end) {
int mid = (start + end) / 2;
long long num = 0;
for(int i = 1; i <= N; i++)
num += min(mid/i, N);
if(num < k)
start = mid + 1;
else {
result = mid;
end = mid - 1;
}
cout<<start<<' '<<end<<' '<<mid<<'\n';
}
cout<<result;
return 0;
}
'백준(Baekjoon) 문제' 카테고리의 다른 글
백준 1463 1로 만들기 (0) | 2019.02.27 |
---|---|
백준 1005 ACM Craft (0) | 2019.02.27 |
백준 10815 숫자카드 (0) | 2019.02.24 |
백준 1920 수 찾기 (0) | 2019.02.24 |
백준 1654 랜선 자르기 (0) | 2019.02.24 |