이 문제는 그 동안 힘들게 풀었던 완전 탐색 문제에 비해서 비교적 쉽게 풀 수 있었다.

표처럼 생각하면 이 문제를 접근하기 더 쉬운데, 갈색과 빨간색 카펫의 칸을 모두 합하면 전체 칸의 수가 된다. 전체 칸 수를 알면 카펫 크기의 가로/세로는 전체 칸 수의 약수가 될 것이다.

예를 들어 brown이 10개, red가 2개면 총 칸의 개수는 12개이다. 따라서 가능한 카펫의 크기는 12의 약수 집합 {1, 2, 3, 4, 6, 12} 중 [6, 2], [4, 3]이 되어 카펫이 이 크기일 때 red 또는 brown의 크기가 동일한지 보면 된다.

카펫 크기 [1, 12], [2, 6] 등이 후보로 설정되지 않은 이유는 문제의 조건에서 가로가 세로보다 같거나 길다고 했기 때문이다. 또 [12, 1]과 같은 경우가 설정되지 않은 이유는 카펫의 높이가 1이면 red가 0이기 때문이다. 그러나 red의 조건은 1 이상이어서 제외했다.

풀이

가로가 세로 크기보다 더 크다고 했기 때문에, 약수 값을 큰 순서대로 검색했다. 그런데 자기 자신은 세로 값이 1이 나오기 때문에, 이는 제외하기 위해서 2로 나눈 값부터 시작했다.

이 때 Math.floor()를 활용해 나눈 값의 내림 값을 사용하도록 했는데, JavaScript에서는 /로 나눈 값이 정수가 아니라 소수 형태가 나올 수 있기 때문이다.

이 크기가 맞는지 확인하는 것은 red값이 맞는지 확인하는 것으로 했다. 테두리를 제외한 모든 값이 red이기 때문에 가로와 세로를 2칸씩 줄인 값을 곱하면 red가 된다.

둘 중 하나만 확인하면 나머지 칸도 그 값이 맞기 때문에 굳이 두 칸이 모두 같은지 확인할 필요는 없다.

난 red의 규칙을 더 먼저 발견해서 red로 확인했을 뿐이다..ㅎㅎ brown은 길이 값을 모두 더한 뒤 중복된 꼭지점 4칸을 빼면 된다.

코드

JavaScript

function solution(brown, red) {
    const totalSpace = brown + red;
    
    for(let i = Math.floor(totalSpace / 2); i > 0; i--){
        if(totalSpace % i !== 0) continue;
        
        const width = i;
        const height = totalSpace / i;
        
        if((width - 2) * (height - 2) === red){
            return [width, height];
        }
    }
}