1️⃣ 서론
백준 문제 1300번 K번째 수 입니다. 파이썬(Python)으로 풀었습니다.
2️⃣ 문제 설명
이 문제는 행,열 인덱스가 1부터 시작하는 N * N 배열을 만들어 K번째 수를 찾는 문제입니다.
배열의 원소는 A[i][j] = i * j 입니다.
3️⃣ 풀이
이 문제는 특이하게 이분탐색 으로 해결이 가능합니다.
일단, k 번째수는 k보다 작거나 같으므로 left를 1, right를 k로 정해줍니다.
그리고 mid를 구해 그 mid 보다 작거나 같은 수의 갯수를 cnt에 저장합니다.
그 이유는 k번째 수를 구하기 위해서는 k보다 작은 수의 갯수를 구해야 하기 때문입니다.
이 말은 즉, k보다 작은 수의 갯수를 알면 k번째 수를 구할 수 있다는 뜻입니다.
cnt 는 N을 초과할 수 없으므로 min을 활용합니다.
또한 행은 i의 배수로 이루어져 있기 떄문에 mid // i 를 통해 갯수를 구합니다.
그럼 소스코드를 보겠습니다.
4️⃣ 소스코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
n = int(input())
a = int(input())
left = 1
right = a
while left <= right:
cnt = 0
mid = (left + right) // 2
for i in range(1, n + 1):
cnt += min(mid // i, n)
if cnt < a:
left = mid + 1
else:
ans = mid
right = mid - 1
print(ans)
5️⃣ 마치며..
질문과 지적은 환영합니다. 이 문제는 최적의 정답일 수도 아닐수도 있습니다.
궁금한게 있으시면 아래 댓글 남겨주세요.🙏
댓글은 저에게 큰 힘이 됩니다!
감사합니다. ❤️
