[Baekjoon]백준 1300 K번째 수(골드 1) - C++, Python

문제설명

문제자체는 매우 간단하다 N×N인 배열 A에는 A[i][j] = i×j의 규칙으로 값이 들어가게 된다

이후 배열 B에 A의 값들을 오름차순으로 넣고, K번째 위치한 수의 값을 구하면 되는 문제이다

사실 이분 탐색 단계임을 모르고 이 문제를 접하였다면, 감을 잡는데 꽤나 오랜 시간이 걸렸을 것 같다

이분 탐색 단계임을 알기 때문에 이를 고려하여 규칙성을 찾고자 노력하였다

 

그리고 당연한 부분에서 규칙을 찾을 수 있었다

어떠한 배열에서 이를 오름차순으로 정렬하였을 때, k번째 index의 값인 J는 해당 배열에서 k번째로 작거나 

같은 수이며, 이를 다르게 해석하면 J보다 작거나 같은 수가 k개 있다는 뜻이다

따라서 N, K를 입력받은 문제조건에서 K를 기준으로 숫자를 찾으면 정렬한 값을 따로 배열에 저장하지 않고

숫자를 찾을 수 있다는 뜻이된다

일단 배열 A에 들어가는 숫자의 규칙을 찾아보자

1 2 3 4

2 4 6 8 

3 6 9 12

4 8 12 16

여기서 K번째 수를 찾으려면 K보다 작은 수가 총 몇개인지 확인하면 된다

이를 확인하는 방법은 나누었을 때의 몫을 확인하면 된다 코드로 설명하자면

for(int i = 1; i <= size; i++)
	cnt += min(size, mid / i);

일단 한 라인에(한 행에) size보다 수의 개수가 많을 수 없다 그리고 mid / i 를 하게 되는데, 여기서 i는 행을 의미한다

첫번째 행부터 마지막 행까지 연산을 하며 cnt의 값을 갱신하는데, 두번째 행은 2의 배수들이므로 mid / 2를 하게된다

그리고 그 기준이 되는 수(mid)를 연산한 결과가 더 작다면 이는 해당 행에는 기준보다 더 큰 수가 존재한다는 뜻이다

이를 활용하여 얻은 cnt의 값을 이전에 이분 탐색할 때 사용한 방법과 동일하게 if, else문을 사용하여

기준치의 값을 더 키울지, 줄일지 결정하면 된다

#include <iostream>
using namespace std;

int main() {
    int size, find_num;
    cin >> size >> find_num;

    int start = 1;
    int end = find_num;
    int result = 0;
    while(start <= end) {
        int mid = (start + end) / 2;
        int cnt = 0;
        for(int i = 1; i <= size; i++)
            cnt += min(size, mid / i);
        if (cnt < find_num)
            start = mid + 1;
        else {
            result = mid;
            end = mid - 1;
        }
    }
    
    cout << result << endl;

    return 0;
}

그런데...컴파일 에러가 발생하였다 뭐지 싶어 헤더에 #include <algorithm>도 추가해보고, 오타도 찾아봤으나

아무 문제가 없었다 심지어 원래는 컴파일 에러의 이유도 알려주지만, 이유도 확인할 수 없는 상태였다

확인해보니 나뿐만 아니라 모든 인원이 컴파일 에러를 겪고 있었다 이를 보니 채점 서버에 문제가 있는듯 하였고,

추후 시간이 지난 후에 다시 제출하였을 때는 정답임을 확인할 수 있었다

컴파일 에러 문제(서버 문제)가 해결된 이후 파이썬으로도 코드를 작성하였고, 이는 다음과 같다

import sys
input = sys.stdin.readline

size = int(input()) 
find_num = int(input())

start = 1
end = find_num
result = 0
while start <= end:
    mid = (start + end) // 2
    cnt = 0
    for i in range(1, size + 1):
        cnt += min(size, mid // i)
    if cnt < find_num:
        start = mid + 1
    else:
        result = mid
        end = mid - 1

print(result)