[C++]백준 - 1300번 문제

1300번: K번째 수 (acmicpc.net)

1300번: K번째 수

 

1300번 : K번째 수

---

세준이는 크기가 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]를 출력한다.

 

 

---

 

생각해 볼 점

---

문제만 보면 시뮬레이션으로 풀어야 할 것 같지만, 배열의 크기를 생각해 볼때, 그 만큼의 배열 공간과 연산을 하는 것은 무리일 것입니다.

 

이분 탐색을 이용하되, 조건 설정이 까다롭습니다.

 

우선, 이분 탐색이므로 left와 right를 설정합니다.

 

left = 0, right = N * N + 1로 설정합니다.

 

mid = (left + right) / 2가 될 것인데, mid의 값을 답으로 가정합니다.

 

예를 들어, N = 3이고, 7번째 수를 구하고자 한다면

 

1 2 3

2 4 6

3 6 9

 

위와 같은 배열이 생성되고, left = 0, right = 10이 됩니다.

 

mid = 5일 것이고, 우리는 5를 답으로 가정합니다.

 

5가 답이라면, 5보다 작거나 같은 수가 최소 7개 있어야 합니다.

 

 

세어보면 7개보단 적습니다. 적다면, Left = mid를 수행 후, 다시 mid를 구해 반복합니다.

 

 

mid = 7일 때, 8개를 세었습니다. 7개 이상이므로 답일 수도 있습니다. 우리는 최솟값을 찾을 것이므로 Right = mid를 수행하고, 반복합니다.

 

mid = 6일 때, 8개를 세어서 6이 답일 수도 있습니다. 마찬가지로, Right = mid를 수행하고, 반복합니다.

 

Right와 Left의 차이가 1이 나게 되면, 수행을 종료하고 Right가 답이 됩니다.

 

 

우리는 육안으로 n보다 작은 수를 셀 수 있었습니다.

 

하지만, 육안이 아니라 알고리즘을 통해 n보다 작은 수의 갯수를 세는 방법은 무엇일까요?

 

잘 보면 위에서 부터 i번 째 행은 i의 배수로만 되어있습니다.

 

따라서, 5보다 작거나 같은 수의 갯수는 (5 / i) 개입니다.

 

그런데, 한 행 당 갯수의 최댓값은 N개 이므로, N개를 넘어가면 N개라고 정정해주어야 합니다.

 

결국, i 행 당 5보다 작거나 같은 수의 갯수는 min(N, 5 / i)가 되겠습니다.

 

코드

---

#include <iostream>
#include <algorithm>
using namespace std;

int main()
{
    long long N, K;
    cin >> N >> K;
    
    long long left = 0, right = N * N + 1;
    while(left + 1 < right)
    {
        long long mid = (left + right) / 2;
        long long count = 0;
        for(long long i = 1; i <= N; i++) count += min(N, mid / i);
        
        if(count < K) left = mid;
        else right = mid;
    }
    
    cout << right;	//조건을 만족하는 가장 작은 값이므로 right를 사용
    return 0;
}

 

그 외

---

int 범위 내에 충분히 들어갈 것 같아 int로 문제를 풀어보았으나, 틀렸습니다.

범위가 어중간하다 싶으면 그냥 long long을 쓰는 것이 좋겠습니다.