[C++][Programmers][완전탐색] 카펫

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

프로그래머스

 

[해결책]

종이에 그려가며 규칙을 찾아보려고 했는데 계속 원점으로 빙빙 돌아서 힌트를 봤다.

3x3이 가장 작은 카펫 크기(가로>=세로 이므로)라는건 구했는데 카펫이 모양이 직사각형일 때, 정사각형일 때로 나눠가며 접근해서 빙빙 돌았던거 같다.

 

1) 가장 작은 세로의 길이는 3 이다.

2) 노란색과 갈색 크기를 모두 합한 값이 넓이이므로 가로x세로 값과 같다.

3) 세로길이를 3부터 1씩 더하며 반복문을 돌면서 가로 값을 찾는다. '노란색+갈색 / 세로 = 가로' 조건을 만족하는 가로 

4) 조건을 만족하는 가로를 찾았다면, 갈색 테두리를 제외한 '(가로 -2) * (세로-2) = 노란색' 을 만족하는지 본다.

5) 이것까지 만족하면 가로 세로를 잘 구한 것.

 

[알아둘 것]

정해진 모양이면 넓이를 사용하는 법도 기억해두기.

 

[코드]

#include <string>
#include <vector>

using namespace std;

vector<int> solution(int brown, int yellow) {
    vector<int> answer;
    int sum = brown + yellow; //갈색 노란색 개수 더해서 넓이 구하기
    
    //최소 높이는 3부터 시작
    for(int height = 3; ; height++){
        int width = sum / height;
        //무조건 갈색인 높이 2줄, 가로 2줄을 제외한 값을 곱했을 때 노란색 값과 같으면 그게 정답.
        if(((height -2)*(width -2))==yellow){
            answer.push_back(width);
            answer.push_back(height);
            break;
        }
    }
    return answer;
}