[프로그래머스, C++] 카펫(완전탐색 파트)

문제 링크

코딩테스트 연습 - 카펫

 

 

 

풀이

그림을 잘 보면

안쪽(노랑)의 width와 전체 카펫의 width는 2개의 격자 차이,

안쪽(노랑)의 height과 전체 카펫의 height은 2개의 격자 차이를 볼 수 있다.

 

따라서, 안쪽 색깔(노랑)의 width와 height을 알기 위해 약수를 구하면서

"(width+2) * (height+2) = 전체 카펫의 격자 개수" 식을 이용한다.

위 식이 참을 나타내는 width+2와 height+2에 대해 리턴해준다.

 

- 참고! width+2 >= height+2 <- 문제에 나와있다.

- 약수를 구할 때는 효율을 위해서 해당 수의 루트까지만 구한다.

- 소수와 마찬가지로, 약수는 일정한 수를 지나면 구할 수 있는 약수가 반복되는 분기점은 루트까지다.

ex) 10의 약수면 1, 2 까지만 구하면 5, 10이 약수임을 알 수 있다, 이에 대해 분기점은 루트까지다.

 

 

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

using namespace std;

vector<int> solution(int brown, int yellow) {
    vector<int> answer;
    
    for(int i=1; i<=sqrt(yellow); i++){     // 약수 구하기
        if(yellow%i != 0) continue;     // 나누어떨어지지 않으면 continue
        int width = i+2;
        int height = yellow/i + 2;
        
        if(brown+yellow != width*height) continue;
        answer.push_back(max(width, height));       // 너비 최대
        answer.push_back(min(width, height));       // 높이 최소 
        break;
    }

    return answer;      // 카펫의 가로, 세로 크기를 순서대로 배열에 담아 리턴
}