카펫 (프로그래머스)

모든 경우를 검사하면서 조건에 알맞은 답을 골라주면 되는 문제였다.

 

노란 격자가 한개라도 들어가기 위해서는 카펫의 크기를 3 x 3부터 시작해야 한다. 조건 중 "카펫의 가로 길이는 세로 길이와 같거나, 세로 길이보다 깁니다."를 주목하자. 이와 같은 정보들은 세로 길이는 절대 가로 길이를 넘어갈 수 없으므로 검사하는 범위를 줄이는데 도움을 줄 수 있다.

 

접근 방법은 다음과 같다.

1. 이중 반복문을 사용한다. i x j 라고 가정했을때 i를 3부터 크게잡아 brown + yellow까지 반복한다. 

2. j는 3부터 i까지 반복한다.

3. yellow의 크기는 brown의 가로, 세로 길이값이 2씩 더 작으므로 yellow 격자의 갯수는 (i - 2) * (j - 2)이다.

4. (i - 2) * (i - 2)가 yellow 갯수보다 작으면 반복문으로 검사를 하더라도 위 조건을 항상 만족하지 않으므로 다음 i값으로 넘어간다. 

5. i와 j 값이 i * j = brown + yellow를 만족하면서, (i - 2) * (j - 2) = yellow격자갯수 라면 정답이므로 더이상 검사할 필요 없이 정답을 입력해 제출하면 된다. 

코드는 다음과 같다.

#include <string>
#include <vector>

using namespace std;

vector<int> solution(int brown, int yellow) {
    vector<int> answer;
    
    int total = brown + yellow;
    for(int i = 3; i <= total; ++i)
    {
        if((i - 2) * (i - 2) < yellow) continue;
        for(int j = 3; j <= i; ++j)
        {
            if(total == i * j && (i - 2) * (j - 2) == yellow) 
            {
                answer.push_back(i);
                answer.push_back(j);
                return answer;
            }
        }
    }
}