algospot.com :: 질문과 답변: 두개의 정수 집합을 Product한 집합에서 다음 큰 수를 찾는 문제

두개의 정수 집합을 Product한 집합에서 다음 큰 수를 찾는 문제

mathguy

안녕하세요. 보기에는 간단한데 쉽게 답이 떠오르지 않는 문제가 있어서 질문드립니다. 제가 우선 간단히 정리해보았는데요.

T= \left \{ i \times j | 1\leq i \leq m, 1\leq j \leq n \textrm{ where } n, m \textrm{ are postive integers }\right\}
$T= \left \{ i \times j | 1\leq i \leq m, 1\leq j \leq n \textrm{ where } n, m \textrm{ are postive integers }\right\}$
\textrm{For a given numbers } {i}', {j}' \textrm{ such that } {i}'\times {j}' = l \in T,
$\textrm{For a given numbers } {i}', {j}' \textrm{ such that } {i}'\times {j}' = l \in T,$
\textrm{Do we have linear time algorithm to get the largest smaller number }
$\textrm{Do we have linear time algorithm to get the largest smaller number }$
k \in T \textrm{ next to } l \textrm{ and its constitutes } {i}'', {j}'' \textrm{?}
$k \in T \textrm{ next to } l \textrm{ and its constitutes } {i}'', {j}'' \textrm{?}$
프로그램에서 Looping을 구현하면서, early termination condition을 찾아보려고 합니다.
이런 문제를 위한 알고리즘이 존재할 것 같기도 한데요. 잘 떠오르지 않아서 질문드립니다.

미리 고수 여러분들의 도움 감사드립니다.

7년 전

1개의 댓글이 있습니다.

keith

k의 condition이 어떻게 되나요?
제가 생각되는 알고리즘은,
k-max(n,m)의 크기가 배열로 메모리에 load 할 수 있을만큼의 사이즈라면 (개당 1바이트 정도면 될듯)
최악의 경우가 k/n + k/m + min(n,m) 가 되는 O(k) 정도입니다.

7년 전 link
정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.