[프로그래머스/C++ 문제 풀이] Lv. 2 - 카펫

문제 설명

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

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

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

제한 사항

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

입출력 예

---

문제 풀이

이번 문제는 직사각형의 가로와 세로 길이를 구하는 문제입니다.

 

문제에서 직사각형의 테두리 길이와, 테두리를 제외한 넓이가 주어지기에 가로, 세로 값을 증가시키며 알맞는 가로, 세로 크기를 구하는 방식으로 문제를 해결하였습니다.

 

예를 들어, 가로가 n, 세로가 m일때 일차원적으로 생각해보자면 중앙 yellow의 크기는 언제나 (n - 2) * (m - 2)이며, 테두리의 길이는 (n * 2) + (m * 2) - 4인 것을 쉽게 알 수 있습니다.

 

즉, 언제나 가로가 세로보다 같거나 길다는 조건이 주어졌기에 가로는 최소 크기인 3부터 순회하며 되며, 세로의 경우 3부터 가로 크기까지만 순회하며 모든 길이를 탐색하는 방식으로 문제를 해결하게 되었습니다.

정답 코드

풀이 시간 : 13m 46s

#include <string>
#include <vector>

using namespace std;

vector<int> solution(int brown, int yellow) {
    vector<int> answer;
    
    // 가로 세로가 n, m일때 중앙의 크기는 다음과 같다.
    // - (n - 2) * (m - 2)
    // - 이를 이용해 가로 세로 크기를 맞추고 Yellow의 수와 일치하는지 확인해보기
    
    // w가 언제나 h보다 같거나 크기에 다음과 같이 순회하도록 합니다.
    for (int w = 3; w <= 2500; w++)
    {
        for (int h = 3; h <= w; h++)
        {
            // 사각형의 테두리 크기 구하기
            int cnt = (w * 2) + (h * 2) - 4;
            
            // 만약 사각형의 테두리가 total과 동일하다면?
            if (cnt == brown)
            {
                // yellow 체크
                if ((w - 2) * (h - 2) == yellow)
                {
                    answer.push_back(w);
                    answer.push_back(h);
                    
                    return answer;
                }
            }
        }
    }
}