42842. 카펫를 풀고 문제를 푼 기록이다. 언어는 JS를 사용하였다.

42842. 카펫

Leo는 카펫을 사러 갔다가 아래 그림과 같이 중앙에는 노란색으로 칠해져 있고 테두리 1줄은 갈색으로 칠해져 있는 격자 모양 카펫을 봤습니다.

Leo는 집으로 돌아와서 아까 본 카펫의 노란색과 갈색으로 색칠된 격자의 개수는 기억했지만, 전체 카펫의 크기는 기억하지 못했습니다.

Leo가 본 카펫에서 갈색 격자의 수 brown, 노란색 격자의 수 yellow가 매개변수로 주어질 때 카펫의 가로, 세로 크기를 순서대로 배열에 담아 return 하도록 solution 함수를 작성해주세요.

제한사항

• 갈색 격자의 수 brown은 8 이상 5,000 이하인 자연수입니다.
• 노란색 격자의 수 yellow는 1 이상 2,000,000 이하인 자연수입니다.
• 카펫의 가로 길이는 세로 길이와 같거나, 세로 길이보다 깁니다.

입출력 예

풀이

간만에 풀어본 완전 탐색 문제이다. DP에 비해서 완전 탐색은 많이 풀어보지 않아서 약간 헤매긴 했는데.. 그래도 검색안해보고 잘 풀어 냈다.

function solution(brown, yellow) {
    const area = brown + yellow;
    let height = 0;
    let width = 0;

    const result = [];
    for (let i = 3; i <= area / 3; i += 1) {
        if (area % i === 0) {
            const tmpHeight = i;
            const tmpWidth = area / i;
            
            if (tmpHeight > tmpWidth) {
                break;
            }

            if (tmpHeight * 2 + (tmpWidth - 2) * 2 === brown) {
                height = height < tmpHeight ? tmpHeight : height;
                width = tmpWidth;    
            }
        } else {
            continue;
        }
    }

    return [width, height];
}

일단 노란색 사각형을 감싸기 위해서는 세로 길이가 무조건 3이상이어야 한다. for문을 통해서 높이를 1씩 증가 시키는데, 일단 해당 i 번째 세로 길이일 때 사각형이 될 수 있는지를 체크한다. 사각형이 되지 못하면 그냥 넘겨버린다.

사각형이 되더라도 세로 길이가 가로보다 길게 되면 break 되는데, 그 이후는 볼 필요도 없이 크기 때문에 break로 for문을 빠져나온다.

이제 사각형도 되고, 세로 길이가 가로 길이보다 만족하는 경우 마지막 체크를 한번 해야 한다. 바로 해당 사각형이 조건에 맞는 사각형인지 체크하는 것이다. 만약 이 체크를 하지 않는다면 단순히 해당 넓이로 만들 수 있는 넓이가 가장 큰 사각형이란 조건이 되버린다.

brown 사각형은 맨 바깥쪽 칸만 차지하므로, 높이 2 + ( 가로 - 2 ) 2로 계산할 수 있다. 가로에서 2를 빼는 이유는 세로값에서 포함되기 때문이다. 해당 값이 입력된 brown 값을 만족하는지 체크하고 만족하면 해당 값을 넣어주면 된다.

꽤 오랜만에 푸는 완전 탐색 문제였는데, 다른 문제보다 시간은 10분정도 더 걸렸지만 재미있게 풀었다.

결과

채점 결과
정확성: 100.0
합계: 100.0 / 100.0