JArchive 프로그래밍 일기

문제

카펫 프로그래머스 level2

리뷰

완전탐색 카테고리의 문제.

카펫의 갈색 격자의 수, 노랑 격자의 수가 주어진다. 카펫의 가로 길이, 세로 길이를 맞춰야 한다.

brown + yellow 를 합치면 카펫의 면적을 알 수 있다.

가로 X 세로 == 면적 이 된다.

예를 들어, 면적이 12라면, 12의 제곱근(면적의 제곱근) 부터 3까지 탐색하면 세로의 길이를 얻을 수 있다.

세로가 3 이상이 되어야 brown이 yellow를 한 줄이라도 둘러쌀 수 있다.

세로가 2라면, yellow 격자는 생길 수 없기 때문이다.

long long sum = brown + yellow; // 면적 
long long hori = 3;  // 세로
long long ver = 1;   // 가로 
int limit =  sqrt(sum); // 면적의 제곱근 

for(hori = 3; hori <= limit; hori++){ // 세로 hori 구하기 

    if( sum % hori == 0){ // 면적과 나누어 떨어지는 세로 길이 발견.
        ver = sum/hori;  // 가로 길이가 정해짐.

    }
}

면적과 나누어 떨어지는 세로 길이를 구했을 때, 아래의 조건을 만족하는지 확인하여 격자의 개수까지 맞춰본다.

(ver-2)*(hori-2) == yellow  

가로 기준으로 봤을 때, brown이 둘러싼 맨 위 한 줄, 맨 아래 한 줄을 빼면 ( hori - 2 ) 가 된다.

세로 기준으로 봤을 때도 맨 왼쪽, 맨 오른쪽 세로줄을 2개 빼면, ( ver - 2 ) 가 된다.

이렇게 격자의 개수를 확인하는 이유는, 특정 면적을 만족시킬 수 있는 가로, 세로의 길이는 여러개가 나올 수 있기 때문이다.

코드

#include <string>
#include <vector>
#include <cmath>
#include <functional>
#include <algorithm> 
using namespace std;

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

    long long sum = brown + yellow; // 면적 
    long long hori = 3;  // 세로
    long long ver = 1;   // 가로 
    int limit =  sqrt(sum); // 면적의 제곱근 

    for(hori = 3; hori <= limit; hori++){ // 세로 구하기 

        if( sum % hori == 0){
            ver = sum/hori; 

            if( (ver-2)*(hori-2) == yellow ){
                answer.push_back(ver); // 가로 
                answer.push_back(hori); // 세로 
                break;                
            }

        }
    }

    return answer;
}