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

안녕하세요 HANCO입니다.

SSAFY 3기를 지내면서 알고리즘 문제를 풀시간이 적어서 가끔 풀게되네요!

오늘은 프로그래머스 완전탐색 카테고리의 카펫 문제를 풀어보았습니다.

완전탐색을 사용해서 푸는 문제인 것 같았는데 약간의 패턴을 찾아서 풀어보았습니다.

문제풀이

[전체코드]

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

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

        // yellow 약수 담을 공간
        vector<int> d;

        // 약수구하기
        for(int i = 1; i <= yellow; i++){
            // yellow가 i값으로 나누어 떨어진다면
            if(yellow % i == 0){
                // 약수를 담는다.
                d.push_back(i);
            }
        }
        // 약수의 개수가 홀수개일때와 짝수개일때를 나눠주었다.
        // 5개면 (5-1)/2 : 0 ~ 2 index까지 (중복수는 같은 수곱)
        // 6개면 (6-1)/2 : 0 ~ 2 index까지
        for(int i=0;i<=(d.size()-1)/2;i++){
            // yellow 세로
            int tmp1 = d[i];
            // yellow 가로
            int tmp2 = yellow / tmp1;

            // 전체 블록 개수
            int tmp = tmp1*2 + tmp2*2 + 4 + yellow;

            // 블록개수가 주어진 brown + yellow 개수와 같다면
            if(brown + yellow == tmp) {
                // 가로, 세로 길이 +2 씩
                tmp1+=2;
                tmp2+=2;
                answer.push_back(tmp2);
                answer.push_back(tmp1);
                break;
            }
        }

        d.clear();
        return answer;
    }

주석으로 코드설명을 적어두었습니다.

감사합니다.