💡 문제
세준이는 크기가 N×N인 배열 A를 만들었다. 배열에 들어있는 수 A[i][j] = i×j 이다. 이 수를 일차원 배열 B에 넣으면 B의 크기는 N×N이 된다. B를 오름차순 정렬했을 때, B[k]를 구해보자.
배열 A와 B의 인덱스는 1부터 시작한다.
입력
첫째 줄에 배열의 크기 N이 주어진다. N은 10보다 작거나 같은 자연수이다. 둘째 줄에 k가 주어진다. k는 min(10, N)보다 작거나 같은 자연수이다.
출력
B[k]를 출력한다.
💭 접근
이 문제를 해결하기 위해선 오름차순 정렬된 배열에서 k번째 수를 찾아야 하므로 k번째 수보다 작은 수가 몇개인지 찾으면 k번째 수를 알아낼 수 있다.
따라서 변수는 다음과 같이 설정했다.
start: 배열에서 가장 작은 원소 (1 x 1) →1
end: 배열에서 가장 큰 원소 (n x n) →n * n
mid: 배열 안의 임의의 원소 → (start + end) // 2
이때 mid가 k번째 수가 되는데, 이를 조절하면서 mid보다 작은 수가 k개 보다 많거나 같을 때를 찾으면 된다. 예제를 보며 이해해보자.
예제 1
n= 3,k= 7
list = [[1, 2, 3], [2, 4, 6], [3, 6, 9]]
1.start= 1,end= 9,mid= 5, (1, 2, 2, 3, 3, 4)
→cnt= 6,cnt<k→mid증가
2.start= 6,end= 9,mid= 7, (1, 2, 2, 3, 3, 4, 6, 6)
→cnt= 8,cnt≥k→ans= 7,mid감소
3.start= 6,end= 6,mid= 6, (1, 2, 2, 3, 3, 4, 6, 6)
→cnt= 8,cnt≥k→ans= 6, 종료
위처럼 임의의 mid 값보다 작거나 같은 값을 찾고 그 값의 개수에 따라 mid값을 조절하면서 최적해를 찾으면 된다.
그렇다면 mid보다 작거나 같은 값의 개수는 어떻게 구할 수 있을까?
ex) 4 x 4 배열에서 7보다 작거나 같은 수의 개수
1 x 1 ~ 1 x 4 = 4개 (1, 2, 3, 4)
2 x 1 ~ 2 x 4 = 3개 (2, 4, 6)
3 x 1 ~ 3 x 4 = 2개 (3, 6)
4 x 1 ~ 4 x 4 = 1개 (4)
위에서 볼 수 있듯이 7에 각 행에 해당하는 수로 나눈 몫을 구하고, 만약 이 몫이 4보다 크다면 4를 더해주면 된다.
cnt= (7//1) + (7//2) + (7//3) + (7//4) = 4 + 3 + 2 + 1 = 10
위 연산을 코드로 나타내면 다음과 같다.
cnt = 0
for i in range(1, n + 1):
tmp = mid // i
cnt += n if tmp > n else tmp 위와 같은 방법으로 mid보다 작거나 같은 수의 개수를 구한 뒤, 아래와 같이 mid값을 조절하며 최적해를 찾아주면 된다.
if cnt >= k:
ans = mid
end = mid - 1
else:
start = mid + 1📒 코드
def binary_search():
start = 1
end = n * n
ans = 0
while start <= end:
mid = (start + end) // 2
cnt = 0
for i in range(1, n + 1):
cnt += n if mid // i > n else mid // i
if cnt < k:
start = mid + 1
elif cnt >= k:
ans = mid
end = mid - 1
return ans
n = int(input())
k = int(input())
print(binary_search())💭 후기
mid 보다 작은 수의 개수를 구하는 방법만 떠올린다면 쉽게 해결할 수 있는 문제였다.
🔗 문제 출처
https://www.acmicpc.net/problem/1300
