ICONS

면접 대비

시간 제한1초메모리 제한128 MB

요약
N이 주어질 때 R<=C이고 R*C>=N을 만족하면서 R+C를 최소화하는 가장 균형 잡힌 R, C를 구합니다.
난이도

쉬움10점 중 3점

유형
수학, 완전 탐색, 이분 탐색
정답자
아직 제출이 없습니다

문제

Dave는 NN개의 아이콘을 가지고 있으며, 이들을 화면에 행과 열로 이루어진 직사각형 격자 형태로 배치하려고 한다.

모든 칸을 반드시 채울 필요는 없다. 한 행 안에서 일부 칸은 비어 있어도 되므로, RR개의 행과 CC개의 열로 이루어진 격자는 칸이 NN개 이상이기만 하면, 즉 R×C≥NR \times C \ge N이기만 하면 모든 아이콘을 담을 수 있다.

Dave는 배치를 최대한 촘촘하게 만들고 싶어 한다. 모든 아이콘을 담을 수 있는 격자들 중에서, 행의 개수와 열의 개수의 합 R+CR + C가 가능한 한 작아지도록 하려고 한다.

NN이 주어질 때, 이러한 최소 격자의 크기를 구하는 프로그램을 작성하라.

입력

한 줄에 자연수 NN (1≤N≤1001 \le N \le 100) 하나가 주어진다. 이는 배치할 아이콘의 개수이다.

출력

두 정수, 즉 행의 개수 RR과 열의 개수 CC를 공백 하나로 구분하여 출력한다. 격자는 R×C≥NR \times C \ge N을 만족해야 하며, R+CR + C는 가능한 한 작아야 한다.

같은 최소 합을 갖는 격자가 여러 개일 수 있으므로, 답을 유일하게 만들기 위해 가장 균형 잡힌 격자를 출력한다. 즉 두 변의 길이가 최대한 비슷하면서 행의 개수가 열의 개수보다 크지 않은 (R≤CR \le C) 격자를 출력한다. 다시 말해, R+CR + C의 최솟값을 SS라 하면 R=⌊S/2⌋R = \lfloor S/2 \rfloor, C=⌈S/2⌉C = \lceil S/2 \rceil이다.

예제4

  1. 예제 1

    입력
    1
    
    예상 출력
    1 1
    
  2. 예제 2

    입력
    2
    
    예상 출력
    1 2
    
  3. 예제 3

    입력
    5
    
    예상 출력
    2 3
    
  4. 예제 4

    입력
    14
    
    예상 출력
    4 4