프로그래머스 완전탐색 카펫

문제 설명

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

카펫 이미지

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

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

제한사항

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

입출력 예

brown	yellow	return
10	2	[4, 3]
8	1	[3, 3]
24	24	[8, 6]

 

---

나의 코드

#include <string>
#include <vector>
#include <cmath>

using namespace std;

vector<int> solution(int brown, int yellow) {
    vector<int> answer(2);
    int width, height;
    int total = brown + yellow;
    int n = 0;
    while (answer[0] == 0 || answer[1] == 0) {
        n++;
        while (total % n != 0 && n < total) { //나눠지는 수 구함.
            n++;
        }
        width = (n > total / n) ? n : total / n;
        height = total / width;
        if (width < 3 || height < 3) continue;
        int i = 1;
        while ((width - 2 * i) > 0 && (height - 2 * i) > 0) {
            if ((width - 2 * i) * (height - 2 * i) == yellow) {
                if ((2 * i * width) + ((height - 2) * 2 * i) == brown) {

                    answer = { width, height };
                }
            }
            i++;
        }
    }
    return answer;
}

주석있는 버전

#include <string>
#include <vector>
#include <cmath>

using namespace std;

vector<int> solution(int brown, int yellow) {
    vector<int> answer(2);
    int width, height;
    int total = brown + yellow;
    int n = 0;
    while (answer[0] == 0 || answer[1] == 0) {
        n++;
        while (total % n != 0 && n < total) { //나눠지는 수 구함.
            n++;
        }
        if (n < 3 || total/n < 3) continue; //n이 입력 범위를 벗어날 경우 다시 n 을 구함.
        width = (n > total / n) ? n : total / n; //가로를 구함
        height = total / width; //세로를 구함
        int i = 1; 
        while ((width - 2 * i) > 0 && (height - 2 * i) > 0) {
            if ((width - 2 * i) * (height - 2 * i) == yellow) { //yellow의 개수를 구함
                if ((2 * i * width) + ((height - 2) * 2 * i) == brown) { //brown의 개수를 구함
                    answer = { width, height }; //만약 구한 yellow와 brown의 개수가 주어진 yellow, brown과 같다면 return
                }
            }
            i++;
        }
    }
    return answer;
}

나의 풀이를 설명하는 그림

 

위의 그림처럼 노란색 부분을 구하기 위해서는 (width - 2i) x (height - 2i)를 하면 되고 갈색 부분을 구하기 위해서는

모든 타일 수 - 노란색 부분 을 하면 됩니다.

 

---

다른 풀이

#include <string>
#include <vector>

using namespace std;

vector<int> solution(int brown, int red) {

    int len = brown / 2 + 2;

    int w = len - 3;
    int h = 3;

    while(w >= h){
        if(w * h == (brown + red)) break;

        w--;
        h++;
    }

    return vector<int>{w, h};
}

- , 전현빈 님의 풀이입니다.

 

w 는 width, h는 height이다.

맨처음 초기화해준 w는 나올 수 있는 가장 큰 width이고 h는 가장 작은 height이다.

w는 항상 h보다 크거나 같기 때문에 while문의 조건을 위와 같이 주었다고 생각된다.

만약 width * height가 brown과 yellow를 더한 것과 같으면 문제의 조건이 충족되므로 while문을 빠져나온다.

그 외의 경우에는 w를 줄이고 h를 늘여서 조건을 찾아 나선다.