보통완전탐색수학

카펫 만들기

카펫의 바깥 한 줄은 갈색, 안쪽은 노란색으로 칠해져 있어요. 갈색 격자 수 brown과 노란색 격자 수 yellow가 주어질 때, 카펫의 [가로, 세로] 를 반환해요.

가로는 세로보다 크거나 같아요. 답은 항상 하나뿐이에요.

전체 격자 수는 brown + yellow 이고, 이는 가로 × 세로 예요. 즉 전체 격자 수의 약수만 후보예요. 후보가 몇 개 안 되므로 하나씩 넣어 확인하면 돼요 — 1주차의 약수 구하기와 4주차의 완전탐색이 만나는 지점이에요.

예시

예시 1

입력: brown = 10, yellow = 2
출력: [4, 3]
설명: 4 × 3 = 12 개 중 안쪽 2 × 1 = 2 개가 노란색이에요.

예시 2

입력: brown = 8, yellow = 1
출력: [3, 3]

예시 3

입력: brown = 24, yellow = 24
출력: [8, 6]

제한 사항

8 ≤ brown ≤ 5,000
1 ≤ yellow ≤ 2,000,000
가로 ≥ 세로 ≥ 3 인 답이 항상 하나 존재해요.

전체 격자 수 total = brown + yellow 의 약수 h 를 세로로 두고 w = total / h 를 가로로 둬요. w ≥ h 이고 (w - 2) * (h - 2) === yellow 이면 답이에요. 1주차처럼 h * h ≤ total 까지만 훑으면 충분해요.

javascript
Copy code
function carpet(brown, yellow) {
  const total = brown + yellow;
  for (let h = 3; h * h <= total; h++) {
    if (total % h !== 0) continue;
    const w = total / h;
    if ((w - 2) * (h - 2) === yellow) return [w, h];
  }
  return [];
}

이전 문제완주하지 못한 선수

다음 문제나선형 순회

예시 테스트만 실행 (Cmd/Ctrl+Enter)

숨김 테스트까지 채점 (Cmd/Ctrl+Shift+Enter)

에디터를 불러오고 있어요…

코드를 작성하고를 눌러 예시 테스트를 확인해 보세요.