[프로그래머스] 완전탐색>카펫

https://programmers.co.kr/learn/courses/30/lessons/42842
오랜만에 프로그래머스 풀었다

가벼운 마음으로 시작했는데 시간이 꽤 걸렸다,,
왜냐면 바보같이 접근했기 때문

이번에는 스케치 시간을 줄여보고자 아이패드에 하는 대신 메모장에 끄적였다
그래서 생각을 조금 더 깊게 하지 못했던 걸려나 ㅜ

brown, yellow 타일의 개수가 주어질 때,
위와 같이 brown의 테두리를 가지며, 중앙에는 yellow타일이 있는 카펫의 크기를 구하는 문제였다

처음에는 brown과 yellow를 더한 숫자를 만들 수 있는 nxm 을 찾아야 한다고 생각해서
완전히 무식한 방법으로 nxm을 찾아나갔다,,

근데 시간초과에 걸려서 어떻게 빠르게 해야하지 생각하다가
그제서야 약수를 구하면 되는 게 생각이 났다

약수를 구하면 된다는 걸 생각하고 나서는 수월하게 풀렸다

그래도 여러 약수 조합 중에서 정답을 찾을 때에는
스케치 단계에서 생각해두었던 아래 식으로 확인할 수 있었다

n + n + ((m-2)x2) = brown // (n x m 일 때)

배울 점

코드를 작성할 때 여러 약수 구하기 알고리즘을 참고했는데
그 중 하나의 약수 i를 찾고난 후에 sum을 i로 나눈 수도 약수가 된다는 것을 이용한 것이 배울 점인 것 같다

CODE

#include <string>
#include <vector>

using namespace std;

vector<int> solution(int brown, int yellow) {
    vector<int> answer;
    int sum = brown + yellow;

    for (int i = 3; i * i <= sum; i++)
    {
        if (sum % i == 0)
        {
            if(i + i + (((sum/i)-2)*2) == brown)
            {               
                answer.push_back(sum/i);
                answer.push_back(i);
                return answer;
            }            
        }         
    }
}