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

문제 설명

Leo는 카펫을 사러 갔다가 아래 그림과 같이 중앙에는 노란색으로 칠해져 있고 테두리 1줄은 갈색으로 칠해져 있는 격자 모양 카펫을 봤습니다.

Leo는 집으로 돌아와서 아까 본 카펫의 노란색과 갈색으로 색칠된 격자의 개수는 기억했지만, 전체 카펫의 크기는 기억하지 못했습니다.

Leo가 본 카펫에서 갈색 격자의 수 brown, 노란색 격자의 수 yellow가 매개변수로 주어질 때 카펫의 가로, 세로 크기를 순서대로 배열에 담아 return 하도록 solution 함수를 작성해주세요.

제한사항

갈색 격자의 수 brown은 8 이상 5,000 이하인 자연수입니다.
노란색 격자의 수 yellow는 1 이상 2,000,000 이하인 자연수입니다.
카펫의 가로 길이는 세로 길이와 같거나, 세로 길이보다 깁니다.

입출력 예

brown	yellow	return
10	2	[4, 3]
8	1	[3, 3]
24	24	[8, 6]

Solution

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

bool comp(int a, int b){
    return a > b;
}

vector<int> solution(int brown, int yellow) {
    vector<int> answer;
    int sum = brown + yellow;
    for(int height = sum / 2; height > 0; height--){
        if(!(sum % height)){
            int width = sum / height;
            if((height - 2) * (width - 2) == yellow){
                answer.push_back(width);
                answer.push_back(height);
                break;
            }
        }
    }
    sort(answer.begin(), answer.end(), comp);
    return answer;
}

우선 규칙을 보면 알겠지만, 중앙에는 노란색으로 칠해 져있고 테두리는 갈색으로 칠해 져 있는 카펫이다. 그리고 갈색, 노란색의 격자 수가 입력으로 들어온다.
어렵게 생각하면 이런 문제는 끝도없이 어렵다. 일단 장땡이라 생각하자. 최소한 직사각형 내에 격자가 몇개가 있는지는 알고있기 때문이다.
우선 확실히 알아둬야하는 것은 높이가 될 수 있는 최대가 어느정도인진 모르겠다만 정사각형이 가장 높게 될 수 있는 직사각형이라고 생각하는 것이다.

아니 그러면 세로는 어쩌란 말입니까?

라는 고민을 하셨다면 주먹을 쥐고 머리를 한대 치는 것을 추천한다. 한번 카펫을 90도 돌려보자.

자 그러면 가능한 모든 높이 경우에 대해서 만약에 전체 격자의 갯수와 높이 값이 나누어 떨어진다면? 그러면 직사각형이 만들어진단 얘기니까 일단 너비를 구해둔다.

if((height - 2) * (width - 2) == yellow){
    answer.push_back(width);
    answer.push_back(height);
    break;
}

그리고 테두리만 갈색이라고 했으니, 테두리에 있는 놈들을 제외하고 나머지 격자들의 갯수가 노랑 격자의 갯수와 같다면, 가능한 정답이기 때문에 answer vector에 입력한다.

정답은 오름차순으로 출력이니까 더이상 설명하지 않겠다.

어렵게 생각하면 끝도 없이 어렵지만 완전탐색인 만큼 최대한 쉽게 생각해보고 컴퓨터에게 일을 떠넘겨보자.