프로그래머스 카펫 : 완전탐색 (C++)

문제 링크: programmers.co.kr/learn/courses/30/lessons/42842

코딩테스트 연습 - 카펫

 

카펫의 가로 세로 길이를 구하는 문제이다.

가로 길이를 x, 세로 길이를 y라고 하자. 테두리 1줄이 갈색이고, 나머지 안쪽은 노란색이라고 했다.

네 변에 접한 타일(갈색 타일)의 개수는 양변의 길이를 두번씩 더하고 겹치는 모서리를 한번 빼준 값인 2x+2y-4이다.

안쪽의 타일(노란 타일)의 개수는 (x-2)*(y-2)이다.

갈색 타일과 노란색 타일을 더한 개수가 x*y임을 이용해서 푸는 문제이다.

 

반복문을 돌면서 조건에 맞는 x(가로 길이)를 찾았다.

 총 타일 개수 x*y를 value라고 뒀다. 그렇기에 일단 반복문 내의 해당 iteration에서 value가 x로 나눠떨어지지 않는다면 조건에 불일치하므로 continue를 사용해 다음 x값을 테스트하도록 했다.

value가 x로 나눠 떨어진다면 위의 타일 개수 식을 활용해 점검한 후 조건에 맞으면 맞는 x와 y를 구한것으로 판단해 값을 리턴한다.

 

#include <string>
#include <vector>
#include <cstdio>

using namespace std;

vector<int> solution(int brown, int yellow) {
    vector<int> answer;
    
    int x, y; //x: answer[0], y: answer[1]
    int value = brown + yellow;
    //brown 개수: 2x + 2y - 4
    //yellow개수: (x-2)*(y-2)
    //brown + yellow: x*y
    
    for(int x = 1 ; x < value ; x++){     
        if(value % x != 0) continue;
        y = value / x;
        if(brown == (2 * x + 2 * y - 4) && yellow == (x - 2) * (y - 2)){
            answer.push_back(y);
            answer.push_back(x);
            return answer;
        }  
    }
    return answer;
}