[프로그래머스]카펫 문제 풀이C++ (완전탐색, 약수 구하기)

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

코딩테스트 연습 - 카펫

[프로그래머스]카펫 문제 풀이C++  (완전탐색, 약수 구하기)

 

제한사항

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

입출력 예

brown                                                                     yellow                                                    return

10	2	[4, 3]
8	1	[3, 3]
24	24	[8, 6]

 

문제 풀이

언듯보면 어려워 보이나 잘 보면 쉽다.

우선 카펫의 가로길이는 세로 길이와 같거나, 세로 길이보다 길다 라는 조건이 있다.

그리고 테두리 1줄은 갈색 격자이다.

 

즉, 총 width 에서 -2칸(양 끝 2칸) , 총 height에서 -2칸(맨 위, 맨 아래 칸) 후 w * h는 노란 격자 영역의 크기가 된다.

 

brown + yellow 는 전체 카펫의 크기이고 이 카펫의 약수를 하나씩 구하면서 (w-2) * (h-2)가 yellow와 같은지 확인한다.

width가 무조건 크다는 조건이 있기에 반복문을 거꾸로 순회하며 검사했다.

vector<int> solution(int brown, int yellow)
{
    vector<int> answer;
    
    int carpet = brown + yellow;
    
    for(int i=carpet/2; i>0; i--)
    {
        if(carpet % i ==0)
        {
            int a = i;
            int b = carpet/i;
            
            if((a-2) * (b-2) == yellow)
            {
                answer.push_back(a);
                answer.push_back(b);
                break;
            }       
        }
    }
    return answer;
}