💻 카펫

분류 : Exhaustive Search (완전 탐색)

사용 언어 : C++

문제 링크

🤔 문제 이해

문제 설명

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

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

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

제한 사항

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

해결 방안

카펫의 둘레 블럭인 brown, 속의 블럭인 yellow를 기준으로 width와 length를 구해야 한다.

while문을 통하여 width(혹은 length)를 점차 높여 조건의 충족되는 값을 찾아야 할 것이다.

💡 문제 풀이

방법 1 )

yellow의 기준으로 width와 length의 변수를 만들어 width를 1씩 높여 조건이 맞을 때까지 반복한다.

#include <string>
#include <vector>

using namespace std;

vector<int> solution(int brown, int yellow) {
    int width = 1, length = 1;  // yellow의 width, length

    while (true) {
        // 만약 조건이 맞을 시 break
        if (2 * width + 2 * length + 4 == brown && width * length == yellow) break;

        // 안 맞을 시 width++
        width++;
        length = yellow / width;
    }

    // 만약 조건이 맞았더라도 제한 사항에 "가로 길이 >= 세로 길이"라는 조건이 있어 swap
    if (width < length) {
        int swap = width;
        width = length;
        length = swap;
    }

    return { width + 2, length + 2 };   // yellow기준으로 만들었으므로 둘 다 +2
}

/*
정확성  테스트
    테스트 1 〉	통과 (0.01ms, 3.95MB)
    테스트 2 〉	통과 (0.01ms, 3.94MB)
    테스트 3 〉	통과 (0.01ms, 3.97MB)
    테스트 4 〉	통과 (0.01ms, 3.96MB)
    테스트 5 〉	통과 (0.01ms, 3.94MB)
    테스트 6 〉	통과 (0.01ms, 3.97MB)
    테스트 7 〉	통과 (0.01ms, 3.96MB)
    테스트 8 〉	통과 (0.01ms, 3.93MB)
    테스트 9 〉	통과 (0.02ms, 3.94MB)
    테스트 10 〉	통과 (0.02ms, 3.96MB)
    테스트 11 〉	통과 (0.01ms, 3.96MB)
    테스트 12 〉	통과 (0.01ms, 3.89MB)
    테스트 13 〉	통과 (0.01ms, 3.95MB)

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

시간 복잡도 : n (n <= 5,000)

yellow의 크기를 기준으로 width와 length를 만든다.
while 문을 통하여 조건에 충족될 때까지 width를 1씩 높여준다.

만약 조건이 충족되더라도 length는 yellow를 width로 나눠 설정하기 때문에 제한 사항이 안 맞을 수 있다.
(가로보다 세로로 긴 직사각형이 될 수 있다.)
그래서 swap 코드를 통하여 예외를 처리할 수 있도록 한다.

return은 yellow를 기준으로 하였기에 둘 다 +2를 해준다.