프로그래머스 42842 - 카펫 (Lv.2)

출처: https://school.programmers.co.kr/learn/courses/30/lessons/42842

// 프로그래머스 42842 - 카펫 (Lv.2)
// https://school.programmers.co.kr/learn/courses/30/lessons/42842

// 문제 설명
// 테두리 1줄은 갈색(brown), 그 안쪽은 노란색(yellow)인 격자 카펫.
// 갈색·노란색 격자 수가 주어질 때 카펫의 [가로, 세로]를 반환하라. (가로 >= 세로)

// 제약 조건
// 8 <= brown <= 5,000, 1 <= yellow <= 2,000,000

// 접근 — 약수 완전탐색 O(sqrt(N))
// 1) 전체 격자 수 total = brown + yellow = 가로(w) * 세로(h)
// 2) 노란 영역은 테두리를 한 칸씩 벗긴 안쪽이라 (w-2)*(h-2) == yellow
// 3) total의 약수쌍 (w, h)를 작은 h부터 훑으며 위 식을 만족하는 쌍을 찾는다

#include <string>
#include <vector>

using namespace std;

vector<int> solution(int brown, int yellow) {
    int total = brown + yellow;          // 전체 격자 수 = 가로(w) * 세로(h)

    // 세로(h)를 작은 약수부터 훑는다. h*h<=total이라 항상 w >= h가 보장됨
    for (int h = 1; h * h <= total; h++) {
        if (total % h != 0) continue;    // h가 약수가 아니면 직사각형이 안 나옴
        int w = total / h;               // 가로는 짝이 되는 나머지 약수
        if ((w - 2) * (h - 2) == yellow) // 테두리를 뺀 안쪽이 노란 격자 수와 같으면 정답
            return {w, h};
    }

    return {};
}

정리

• 카펫 전체 칸 수는 brown + yellow이고, 이는 곧 가로 * 세로다. 그래서 문제는 total = brown + yellow를 두 변의 곱으로 쪼개는 약수 분해로 환원된다. 가능한 (가로, 세로) 후보는 total의 약수쌍뿐이라 탐색 공간이 처음부터 작다.
• 노란 영역은 테두리 한 줄을 사방에서 벗긴 안쪽이므로 (w-2) * (h-2)다. 약수쌍 중 이 값이 yellow와 일치하는 쌍이 정답이고, 그런 쌍은 유일하다. 그래서 식 하나로 후보를 바로 거른다.
• 반복 범위를 h * h <= total로 잡은 게 핵심이다. 세로 h를 작은 약수부터 올리면 짝이 되는 가로 w = total / h는 자동으로 w >= h가 되어, 별도 비교 없이 “가로 >= 세로” 조건이 충족된다. 약수는 sqrt(total)까지만 보면 다 나오므로 시간복잡도도 O(sqrt(total))로 충분히 빠르다.
• 굳이 2차방정식(w+h = brown/2 + 2, w*h = total)을 세워 근의 공식으로 풀 수도 있지만, 부동소수점 오차와 정수 캐스팅을 신경 써야 한다. 제약이 total 최대 약 200만이라 약수 완전탐색이면 분기 없이 안전하고 읽기도 쉽다.
• 검증: 예제 (10, 2) → [4, 3], (8, 1) → [3, 3], (24, 24) → [8, 6] 모두 통과(MSVC /std:c++17 컴파일·실행).