문제 설명
정수 격자점(좌표가 모두 정수인 점) 위에 N개의 조약돌을 원하는 위치에 놓을 수 있습니다. 이때 놓인 조약돌들을 모두 포함하는 축에 평행한 직사각형을 만들고, 이 직사각형의 둘레를 최소화하는 것이 목표입니다.
단, 직사각형의 가로와 세로 길이는 각각 최소 1 이상이어야 합니다. 조약돌이 한 줄이나 한 점에 몰려 있어도 길이가 0이 되지 않고 1로 간주합니다.
입출력
- 입력: 조약돌의 개수 N (1 ≤ N ≤ 500,000,000)
- 출력: 최소 둘레
예제
| 입력 | 출력 |
|---|---|
| 5 | 6 |
| 14 | 12 |
핵심 아이디어
격자점 배치 패턴
아래 그림은 N=1부터 N=10까지 조약돌을 최적으로 배치한 패턴을 보여줍니다.
패턴을 관찰하면 핵심 규칙이 보입니다:
- 가로 a, 세로 b인 직사각형에는 최대
(a+1) × (b+1)개의 격자점이 존재합니다. - 둘레를 최소화하려면 직사각형이 정사각형에 가까워야 합니다. (a+b가 일정할 때 둘레는 같지만, 담을 수 있는 점의 수는 a≈b일 때 최대)
- N개의 점을 배치하려면
(a+1) × (b+1) ≥ N을 만족하는 가장 작은 직사각형을 찾으면 됩니다. - 정사각형으로 점을 배치하고 난 뒤 다음 크기의 정사각형을 완성하기 위한 ㄱ자 부분에 점이 하나라도 더 있으면 한 방향으로 사각형의 길이가 1 늘어나 평행한 두 직선이 1 길어져 둘레가 2 증가.
- ㄱ자 부분의 점 개수가 현재 정사각형의 한 변에 들어가는 점 개수를 넘으면 길이 2가 추가됨.
배치 예시
| N | 필요한 직사각형 | 격자점 수 | 둘레 |
|---|---|---|---|
| 1~4 | 1×1 | 2×2 = 4 | 4 |
| 5~6 | 2×1 | 3×2 = 6 | 6 |
| 7~9 | 2×2 | 3×3 = 9 | 8 |
| 10~12 | 3×2 | 4×3 = 12 | 10 |
| 13~16 | 3×3 | 4×4 = 16 | 12 |
수학적 분석
문제 재정의
직사각형의 가로를 a, 세로를 b라 하면:
- 담을 수 있는 격자점 수:
(a+1) × (b+1) - 둘레:
2(a + b)
N개의 점을 담으려면 (a+1)(b+1) ≥ N이어야 하고, a + b를 최소화해야 합니다.
변수 치환으로 단순화
w = a + 1, h = b + 1로 치환하면:
- 조건:
w × h ≥ N(w, h ≥ 2) - 최소화 대상:
2(w + h - 2) = 2(w + h) - 4
즉, w × h ≥ N을 만족하면서 w + h를 최소화하는 문제입니다.
최적해 도출
w × h ≥ N일 때 w + h가 최소가 되려면 w와 h가 √N에 가까워야 합니다.
q = ⌊√N⌋라 하면:
- N ≤ q²인 경우: q×q 직사각형에 담을 수 있음
- w = h = q
- 둘레 = 2(q-1 + q-1) = 4(q-1)
- q² < N ≤ q(q+1)인 경우: 한 변만 1 늘림
- w = q+1, h = q (또는 반대)
- 둘레 = 2(q + q-1) = 4q - 2
- q(q+1) < N ≤ (q+1)²인 경우: 두 변 모두 1 늘림
- w = h = q+1
- 둘레 = 2(q + q) = 4q
공식 정리
d = N - q²라 하면:
둘레 = 2 × (2(q-1) + [d > 0] + [d > q])여기서 [조건]은 조건이 참이면 1, 거짓이면 0입니다 (Iverson 괄호).
공식 검증
| N | q = ⌊√N⌋ | d = N - q² | d > 0? | d > q? | 계산 | 둘레 |
|---|---|---|---|---|---|---|
| 4 | 2 | 0 | 0 | 0 | 2×(2+0+0) | 4 |
| 5 | 2 | 1 | 1 | 0 | 2×(2+1+0) | 6 |
| 6 | 2 | 2 | 1 | 0 | 2×(2+1+0) | 6 |
| 7 | 2 | 3 | 1 | 1 | 2×(2+1+1) | 8 |
| 9 | 3 | 0 | 0 | 0 | 2×(4+0+0) | 8 |
| 14 | 3 | 5 | 1 | 1 | 2×(4+1+1) | 12 |
코드 및 설명
from math import isqrt
n = int(input())
if n < 5:
print(4)
else:
q = isqrt(n) # √N의 정수 부분
d = n - q * q # N에서 q²을 뺀 나머지
print((2 * (q - 1) + (d > 0) + (d > q)) << 1)코드 상세 분석
1. 특수 케이스 처리: N < 5
if n < 5:
print(4)N이 1, 2, 3, 4일 때는 모두 1×1 직사각형(격자점 4개)에 담을 수 있습니다. 최소 둘레는 2×(1+1) = 4입니다.
2. 정수 제곱근 계산
q = isqrt(n)isqrt(n)은 ⌊√N⌋을 반환합니다. 이 값은 N개의 점을 담을 수 있는 기본 정사각형의 한 변 길이 + 1을 의미합니다.
예를 들어 N=14이면 isqrt(14) = 3이므로, 기본적으로 3×3 = 9개의 점을 담는 2×2 직사각형을 고려합니다.
3. 초과분 계산
d = n - q * qd는 q×q개를 초과하는 점의 수입니다. 이 값에 따라 직사각형을 얼마나 확장해야 하는지 결정됩니다.
d = 0: 확장 불필요 (완전 제곱수)0 < d ≤ q: 한 변만 1 확장d > q: 두 변 모두 1 확장
4. 둘레 계산
print((2 * (q - 1) + (d > 0) + (d > q)) << 1)이 부분을 분해하면:
2 * (q - 1): 기본 정사각형(q×q 점 → (q-1)×(q-1) 직사각형)의 가로+세로(d > 0): 초과분이 있으면 1, 없으면 0 → 한 변 확장 여부(d > q): 초과분이 q보다 크면 1, 아니면 0 → 다른 변 확장 여부<< 1: 2를 곱함 (둘레 = 2 × (가로 + 세로))
왜 d > q인가?
q×q 격자에서 한 행(또는 열)만 추가하면 q개의 점이 추가됩니다. 따라서:
d ≤ q: 한 행/열 추가로 충분d > q: 한 행과 한 열 모두 추가 필요
시간복잡도
- 시간복잡도: O(1)
isqrt(n): O(1) (내부적으로 Newton-Raphson 또는 비트 연산 사용)- 나머지 연산: 모두 상수 시간
- 공간복잡도: O(1)
- 사용하는 변수: n, q, d 세 개뿐
N이 최대 5억이지만, 수학적 공식을 사용하므로 입력 크기와 무관하게 즉시 계산됩니다.
정리
이 문제의 핵심은 "N개의 격자점을 담는 최소 둘레 직사각형"을 수학적으로 모델링하는 것입니다.
- 직사각형 (a×b)에 담을 수 있는 격자점 수는 (a+1)×(b+1)
- 둘레를 최소화하려면 정사각형에 가깝게 → √N 기준으로 판단
- q = ⌊√N⌋를 구하고, 초과분 d에 따라 확장 여부 결정
- 최종 둘레 = 2 × (2(q-1) + [d>0] + [d>q])
O(1) 시간에 해결할 수 있는 깔끔한 수학 문제입니다.
