C++로 n개 픽셀에 맞는 직사각형 화면 크기 구하기

숫자 n이 주어졌다고 가정해 봅시다. 디스플레이에는 총 n개의 픽셀이 표시되며, 우리는 이를 만족하는 직사각형 화면의 크기를 찾아야 합니다. 조건은 다음과 같습니다.

행의 개수(a)는 열의 개수(b)를 초과하지 않아야 합니다 [a <= b]
b와 a의 차이(b - a)는 가능한 한 최소여야 합니다

예를 들어 입력이 n = 12라면, 출력은 (3, 4)가 됩니다.

풀이 접근 방법

이 문제를 해결하기 위해 다음 단계를 따릅니다.

i := n의 제곱근
while n mod i가 0이 아니면:
   (i를 1씩 감소)
return (i, n / i)

알고리즘 원리

n의 제곱근에서 시작해 아래로 내려가면서 n을 나누어 떨어지게 하는 가장 큰 약수를 찾습니다. 그 값이 행의 개수(a)가 되고, n을 a로 나눈 몫이 열의 개수(b)가 됩니다. 제곱근 근처에서 약수를 찾으면 두 수의 차이가 자연스럽게 최소화되므로 별도의 추가 비교 없이 조건을 만족합니다. 시간 복잡도는 O(√n)으로 매우 효율적입니다.

예제 코드

아래 구현을 통해 더 잘 이해할 수 있습니다.

#include <bits/stdc++.h>
using namespace std;
void solve(int n){
   int i = sqrt(n);
   while (n % i)
      i--;
   cout << i << ", " << n / i;
}
int main(){
   int n = 12;
   solve(n);
}

입력

출력

3, 4