[코테] 카펫 (완전탐색)

카펫 (완전탐색)

2026.4.25. (작성일 2026.4.27)

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

핵심 개념

약수 구하기

• 약수 구하기는 보통 Lv. 0, Lv. 1에서 그 자체만 나오는 개념 같음. 여기서는 그걸 풀이의 일부로 이용함!
• 방법은 여러가지가 있겠으나 세가지를 정리해둔다.

1. for문이나 while문을 돌려, 나누었을 때 나머지가 0이면 배열에 추가하는 방법
   (가장 직관적. 그러나 모든 수에 대해 반복하므로 다소 비효율적)

2. 약수는 1 * 자기자신, 2 * 자기자신 / 2, ... 와 같이 진행됨(물론 자기자신 / 2가 자연수여야 포함됨). 즉, 자기자신을 제외하면 약수의 최댓값은 자기자신 / 2이므로, 그 값까지만 반복문을 돌려 약수를 구하고 최종 결과 배열에 자기자신을 추가로 넣어줘도 됨. => 반복문 횟수가 방법 1에 비해 절반으로 줄어듦

3. 제곱근 이용 (Math.sqrt() 메서드)
   n의 약수는 루트 n을 기준으로 대칭적임.
   (예) 12의 약수 = 1, 2, 3, 4, 6, 12 = 루트 12(약 3.46)를 기준으로 [1, 12], [2, 6], [3, 4]와 같이 쌍을 이루며 존재함. (쌍으로 곱해서 12가 되는 숫자들이니까 당연)
   => 루트 n까지만 반복문을 돌리되, 나누었을 때 나머지가 0이면 그 숫자와 쌍을 이루는 수까지 한번에 결과 배열에 넣어줌. 실행 후 결과 배열에 중복이 없도록 변경 한번 해주기.

이 글 과 구글 검색 (키워드: javascript 약수 구하기) 결과를 참고했다.

내 풀이

function solution(brown, yellow) {
    // 노란 사각형의 가로를 x, 세로를 y라고 하면,
    // 1. yellow = x * y
    // 2. (brown - 4) / 2 = x + y (모서리를 뺀 가로, 세로)
    // 3. 문제 제한사항에 따라, x >= y
    
    // 곱해서 yellow가 되는 모든 두 자연수에 대해, 위 2, 3을 만족하는 x, y를 구하고,
    // [x + 2, y + 2]를 반환한다.
    
    // 1. yellow의 약수 구하기
    // n의 약수는 루트 n을 기준으로 대칭적임을 이용,
    // 반복할 횟수를 효율적으로 줄여 약수를 구함
    let x = yellow;
    let y = 1;
    
    for (let i = 0; i <= Math.sqrt(yellow); i++) {
        // 약수인지 확인
        if (yellow % i === 0) {
            // x >= y를 만족하도록 i 자신과, 대칭되는 쌍인 (yellow / i)를 할당함
            x = yellow / i;
            y = i;
            
            // 2. (brown - 4) / 2가 x + y인 경우를 찾으면 즉시 종료
            if (x + y === (brown - 4) / 2) {
                break;
            }
        }
    }
    
    // 카펫의 가로, 세로 길이는 yellow의 가로(x), 세로(y) 길이에 모서리 길이를 더한 값
    return [x + 2, y + 2];
}

예제를 그림으로 그려보며 접근했다. 그려보니 바깥 테두리는 모서리 4개가 있고, 그 안의 개수는 노란색 타일의 가로, 세로 길이와 가로, 세로가 서로 같음이 보였다. 노란색의 가로 * 세로 = 2 * (노란색 가로 + 세로) = 갈색 타일 수 - 4, 이것을 만족하는 가로, 세로 숫자의 쌍 1개가 존재함.

이렇게 정리했다.

노란 사각형의 가로를 x, 세로를 y라 할 때, 아래 세 조건을 만족하는 x, y를 구하기

1. (brown - 4) / 2 = x + y
2. yellow = x * y
3. x >= y

x, y를 구했다면 answer = [x + 2, y + 2]

처음엔 미지수가 2개이고 수식도 2개면 방정식으로 답 구할 수 있는 건가 하면서 풀어보려 했는데 좀 복잡해져서 안 풀리길래 멈추고 다시 내가 쓴 걸 봤다.
=> 곱해서 yellow가 되는 두 자연수에 대하여, 조건 1, 3을 만족하는 것을 구해야겠다.

=> 곱해서 yellow가 되는 자연수는 어떻게 구하나? => 약수 구하기

개선된 풀이

function solution(brown, yellow) {
    // 노란 사각형의 가로를 x, 세로를 y라고 하면,
    // 1. yellow = x * y
    // 2. (brown - 4) / 2 = x + y (모서리를 뺀 가로, 세로)
    // 3. 문제 제한사항에 따라, x >= y
    
    // 곱해서 yellow가 되는 모든 두 자연수에 대해, 위 2, 3을 만족하는 x, y를 구하고,
    // [x + 2, y + 2]를 반환한다.
    
    // 1. yellow의 약수 구하기
    // n의 약수는 루트 n을 기준으로 대칭적임을 이용,
    // 반복할 횟수를 효율적으로 줄여 약수를 구함
    let x = yellow;
    let y = 1;
    
    for (let i = 1; i <= Math.sqrt(yellow); i++) { // ✅ 0부터 시작하면 NaN
        // 약수인지 확인
        if (yellow % i === 0) {
            // x >= y를 만족하도록 i 자신과, 대칭되는 쌍인 (yellow / i)를 할당함
            x = yellow / i;
            y = i;
            
            // 2. (brown - 4) / 2가 x + y인 경우를 찾으면 즉시 종료
            if (x + y === (brown - 4) / 2) {
                break;
            }
        }
    }
    
    // 카펫의 가로, 세로 길이는 yellow의 가로(x), 세로(y) 길이에 모서리 길이를 더한 값
    return [x + 2, y + 2];
}

핵심 차이

• 반복문을 0부터 시작하면, yellow % 0 = NaN이라 의미없는 연산. 0부터 시작할 이유가 없음. 1부터 시작으로 변경
• 1 ~ Math.sqrt(yellow)까지 오름차순(i++) 탐색도 가능하고, Math.floor(Math.sqrt(yellow)) ~ 1까지 내림차순(i--) 탐색도 가능함. 문제 테스트 케이스에선 두번째 방법이 전반적으로 조금 더 빠르게 실행되는데, 카펫의 모양이 `1 n, 2 n / 2` 이런 것보다 서로 비슷한 숫자인 경우가 좀더 많은 게 아닐까 싶다.

막혔던 포인트

• 약수 구하는 법!

풀면서 찾은 개념

• 약수 구하기
• Set의 add. 약수 자체를 구하려 했을 때 중복 제거 과정을 추가하지 않으려고 Set으로 썼는데, add를 해도 최종 결과물에 add한 값들이 들어가지 않았다. 이상해서 다시 배열로 바꿨다.
• 위와 같은 접근법에서 Set을 배열로 만들려고 Array.from() 같은 배열 생성 방법도 찾아봤다.
• 쓰면서 이상해서 지금 풀이에 Set 정의랑 add 넣어서 다시 테스트해봤는데 잘 들어간다. 왜 이상했을까..? for문 안에서 매번 새로운 Set을 만들었으려나.. 근데 반복문 밖에서 Set을 로그 찍을 수 없었을텐데.. 실행했을 때 계속 {}가 찍혔던 게 기억난다.

다음에 비슷한 문제 만나면

• 약수는 Math.sqrt()까지 반복문 돌려서 0으로 나누어떨어지는 자연수의 쌍을 구하면 됨!
• 그리고 Set, add 썼을 때 이상하게 빈 값으로 출력된다면, add 직후에 현재 Set의 상태를 로깅하면서 풀어보자.