[프로그래머스] 카펫 (C++)

[아이디어]

그냥 구현 하는 식으로 풀었습니다.

 

 

[요약]

입력 받은 yellow 블록 수에 알맞은 사각형의 형태를 만들어

이 사각형을 brown 블록으로 감쌀 수 있는지 없는지 알아보는 문제였습니다.

 

 

[방법]

yellow 블록 수는 사각형의 넓이 입니다.

yellow의 블록 수의 모든 약수를 구한다면 x개의 사각형에 대한 가로 세로 길이를 구할 수 있습니다.

예)

yellow 블록 수 = 24

24의 약수는 {1,2,3,4,6,8,12,24}

가로 길이가 24라면 세로 길이는 1,

가로 길이가 12라면 세로 길이는 2,

...

 

이렇게 구한 x개의 사각형에 대해

가로 길이의 2배

+

세로 길이의 2배

+

모퉁이 수 4개

=

brown 블록 수

의 식을 세울 수 있었습니다.

 

따라서,

yellow의 수에 대한 약수의 한 쌍을

각각 가로 세로 길이로 하여

brown 블록 수와 비교해주면 끝.

 

 

[설명]

get_divisor()

이 함수는 파라미터 num에 대한 약수를 찾는 함수입니다.

이렇게 찾은 약수를 각각 length_v, width_v 벡터에 추가해 줍니다.

 

isSame(가로, 세로, brown블록 수)

이 함수는 위에서 언급한 식에 대해

brown값과 비교해

같은지 다른지 판별하는 식입니다.

 

 

[코드]

#include <string>
#include <vector>

using namespace std;

#define FOR(i,s,e) for(int i=s; i<e; ++i)

vector<int> length_v; // 약수 저장
vector<int> width_v; // 약수 저장

void get_divisor(int num) {
    /*
    num에 대한 약수를 찾는 함수
    */
    FOR(i, 1, num + 1) {
        if ((num % i) != 0) continue; // 나누어 떨어지지 않으면 약수가 아님
        if (i > (num / i)) break; // 세로 길이가 가로 길이보다 길면 안됨
        length_v.push_back(i);
        width_v.push_back(num / i);
    }
}

bool isSame(int n1, int n2, int brown) {
    /*
    yellow를 감싸고 있는 brown의 크기는 항상
    yellow의 가로길이의 2배, 세로길이의 2배에 모퉁이 4개를 더한 값이다.
    */
    int width = n2 * 2;
    int length = n1 * 2;
    int corner = 4;

    /*
    num은 yellow의 크기에 대해 테두리를 감싼 크기
    */
    int num = width + length + corner;

    if (num == brown) return true; // brown과 같다면 찾고자 하는 가로 세로 길이임
    else return false;
}

vector<int> solution(int brown, int yellow) {
    vector<int> answer;

    get_divisor(yellow);

    FOR(i, 0, length_v.size()) {
        if (isSame(length_v[i], width_v[i], brown) == true) {
            answer.push_back(width_v[i] + 2);
            answer.push_back(length_v[i] + 2);
        }
    }

    return answer;
}

 

[문제 링크]

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

프로그래머스