프로그래머스 - 카펫

programmers.co.kr/learn/courses/30/lessons/42842

코딩테스트 연습 - 카펫

 

brown 과 yellow 두 변수를 합한것이 전체 격자의 갯수이며,

전체 격자의 갯수로 부터 가능한 이차원 행렬은 약수를 통해서 구할 수 있다.

위의 두변수를 합한 결과가 12 라면 12의 약수 1, 2, 3, 4, 6, 12 에서 

약수 두 쌍을 추려내서 1 * 12 행렬, 2 * 6 행렬, 3 * 4 행렬 을 만들어 낼 수 있고,

문제의 조건에서 "카펫의 가로 길이는 세로 길이와 같거나, 세로 길이보다 깁니다." 라 하였으므로,

가로의 길이가 더 큰 행렬로 잡아주면 된다.

그리고 brown 은 이차원 행렬의 겉 부분이므로 상, 하, 좌, 우 4방향을 겉 부분만 돌면서 격자의 갯수를 세고

그 격자의 갯수가 brown 변수와 같으면 문제에서 찾는 값이므로, 프로그램을 종료한다.

 

 

- c++

 

#include <bits/stdc++.h>
 
using namespace std;
 
vector<int> solution(int brown, int yellow) {
    vector<int> answer;
    int total = brown + yellow;
    
    vector<pair<int, int>> vec;
    for (int i = 1; i <= total; ++i) 
        if (total % i == 0) 
            vec.push_back(make_pair(i, total / i));
    
    for (int i = 0; i < vec.size(); ++i) {
        int x = vec[i].first, y = vec[i].second; // 가로 , 세로
        if (x < y) continue;
                
        int cnt = 0;
        
        // E
        for (int j = 0; j < x; ++j) cnt++;
        
        // S
        for (int j = 1; j < y; ++j) cnt++;
        
        // W
        for (int j = x - 2; j >= 0; --j) cnt++;
        
        // N
        for (int j = y - 2; j > 0; --j) cnt++;
        
        if (cnt == brown) {
            answer.push_back(x);
            answer.push_back(y);
            break;
        }
    }
    
    return answer;
}