[c++] 프로그래머스 - 카펫(Level 2)

문제

코딩테스트 연습 - 카펫

 

코드

#include <string>
#include <vector>

using namespace std;
struct Coordinate{
    int x;
    int y;
};

vector<int> solution(int brown, int yellow) {
    vector<int> answer;
    vector<Coordinate> v;
    int x=1; int y = brown+yellow;
    
    while(x<y){
        y = (brown+yellow)/x;
        if(x*y==brown+yellow)v.push_back({x,y});
        x++;
    }
    
    for(int i=0; i<v.size(); i++){
        int x = v[i].x-2;
        int y = v[i].y-2;
        if(x*y==yellow){
            answer.push_back(y+2);
            answer.push_back(x+2);
        }
    }
    return answer;
}

 

풀이(22분)

크게 어렵지 않은 문제였습니다. 원리만 이해하면 구현하기 쉬운데 아래의 입출력으로 한번 설명해 보겠습니다.

brown	yellow	return
24	24	[8,6]

위 입출력에서 나올 수 있는 모든 크기의 결과는 아래와 같습니다. (가로길이가 세로 길이보다 같거나 큽니다.)

• 48 x 1 (가로 x 세로)
• 24 x 2 (가로 x 세로)
• 16 x 3 (가로 x 세로)
• 12 x 4 (가로 x 세로)
• 8 x 6 (가로 x 세로)

그리고 brown같은 경우는 테두리에만 칠해져 있기 때문에 테두리를 제외한 나머지는 전부 yellow가 되어야 한다고 알 수 있습니다. 따라서 yellow의 경우 {가로-2(위&아래) x 세로-2(좌&우)} = yellow개수 가 되어야 한다는 사실을 알 수 있습니다.

따라서 위에서 구한 6개의 경우 중 위 식을 만족하는 경우를 찾아서 반환해주면 정답입니다.