설명 참조
나의 풀이
N = int(input())
k = int(input())
start, end = 1, k
answer = 0
while start <= end:
count = 0
mid = (start + end) // 2
for i in range(1, N + 1):
count += min(mid // i, N)
if count >= k:
answer = mid
end = mid - 1
else:
start = mid + 1
print(answer)
-
처음에 흔하게 이중 for문을 사용해서 제출했더니 메모리 초과로 실패했다.
-
이것을 이분 탐색으로 어떻게 접근해야 하는가 고민에 고민을 해봤지만 혼자서 해결을 못했고, 설명을 참조하였다.
-
우선 N의 행과 열을 갖는 2차 배열의 형태는 이런 모습이다.
-
보면 규칙이 있는데 1행은 1단, 2행은 2단, 3행은 3단 이런식으로 각 행의 인덱스에 맞는 구구단 패턴을 갖고있다.
-
이러한 패턴을 활용해서 문제를 해결할 수 있었다.
-
우선 B[k]의 숫자를 이분 탐색을 사용하여 구해야 한다. 이 값을 구하기 위해 start는 1, end는 k로 두어 중간 값인 mid를 임의의 값으로 계산을 진행한다.
-
만약 k가 7이라면 임의의 값 mid는 4[(1 + 7) // 2] 가된다. 이제 각 행마다 4보다 작거나 같은 값의 개수를 구해주면 된다. 4보다 작거나 같은 값의 개수를 구하는 방법은 구구단 패턴을 이용하여 4를 각 행의 번호로 나눠주면 된다.
1행 : 4 // 1 == 4
2행 : 4 // 2 == 2
3행 : 4 // 3 == 1
이렇게 하면 각 행에서 4보다 작거나 같은 숫자의 개수는 7개가 나온다. 하지만 현재 행과 열은 N개로 제한되어 있다. 그렇기 때문에 이를 맞춰주기 위해서 개수가 N을 넘어버린다면, 해당 행에서 조건을 만족하는 숫자의 개수는 N개가 되어야 한다. -
이것을 소스코드로 표현하면 이렇게 된다.
for i in range(1, N + 1):
count += min(mid // i, N)- 이 소스코드를 통해서 각 행마다 mid 값 보다 작거나 같은 값의 개수를 구할 수 있다. 이 개수를 count 변수에 저장한다.
- count 변수가 만약 k보다 크거나 같다면, answer = mid 를 해주고 count가 많다는 것은 mid 값이 크다는 것이기 때문에 end = mid - 1을 하여 범위를 줄여준다.
- count 변수가 작다면 범위를 늘리기 위해 start = mid + 1을 해준다.
- 반복이 끝나고 answer 값을 출력해주면 된다.
느낀점
설명을 보고도 몇몇 부분은 이해가 가지 않아서 풀이에 대한 설명이 매우 횡설수설하다. 다양한 이분 탐색 문제에대한 경험이 필요하다.
