목록k번째 수 (1)

Don't give up!

[백준] 1300번 : K번째 수 (java)

1300번: K번째 수 (acmicpc.net) 1300번: K번째 수 세준이는 크기가 N×N인 배열 A를 만들었다. 배열에 들어있는 수 A[i][j] = i×j 이다. 이 수를 일차원 배열 B에 넣으면 B의 크기는 N×N이 된다. B를 오름차순 정렬했을 때, B[k]를 구해보자. 배열 A와 B www.acmicpc.net 어떻게 생각하고 문제를 풀었는가? NxN 배열의 각 원소가 갖는 값은 행 또는 열의 배수로 지정되어 있습니다. 따라서 각 행에서 x보다 작은 값의 개수는 x/i와 N 중에서 작은 값으로 구할 수 있습니다. (x값이 ixN보다 큰 값을 갖는 경우가 존재함) 따라서 B[k]는 x보다 작거나 같은 값을 갖는 원소의 수가 k개 이상인 x를 찾음으로써 답을 구할 수 있을 것이라고 생각하였습니다..
Coding Test/BOJ 2021. 8. 20. 19:35
이전 Prev 1 Next 다음