[프로그래머스] Lv.2 카펫 c++

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

프로그래머스

 

카펫은 테두리는 갈색, 중앙은 노란색으로 구성되어 있다.

• brown은 최소 8 최대 5,000이하의 자연수
• yellow는 1이상 2,000,000이하의 자연수
• 카펫 가로길이 >=  카펫 세로길이

ex) brown = 10, yellow = 2인 경우 카펫의 크기는 [4, 3]이 된다.

     *****

     *&&*

     ***** 

즉, brown격자의 개수와 yellow격자의 개수가 주어지면 카펫의 가로, 세로 길이를 구하면 된다.

 

풀이 방법

완전탐색으로 구할 수 있다.

이중 for문을 돌릴때 보통 1초의 제한이 있으므로 10000*10000 안에서는 안전하다.

가로 세로의 크기 기준으로 for문을 돌릴때 yellow의 최대 크기를 고려하여 2500으로 제한했다.

if문에서 3가지 조건을 만족해야 하는데, 

1. (i-2) * (j-2) == yellow (노란색 영역의 크기 검증)

2. brown + yellow == i*j (전체 카펫의 크기 검증)

3. i >= j (가로가 세로보다 크거나 같을 경우)

세가지 경우를 만족하면 break문이 걸리고 for문에서 빠져나온다.

풀이 코드

#include <string>
#include <vector>
using namespace std;
//최대 10000*10000 이하면 가능
vector<int> solution(int brown, int yellow) {
    vector<int> answer;
    for(int i=3; i<=2500; i++){ //가로 길이 탐색
        for(int j=3; j<=2500; j++){ //세로 길이 탐색
            if(((i-2)*(j-2) == yellow) && (brown+yellow) == i*j && i>=j){
                answer.push_back(i);
                answer.push_back(j);
                break;
            } 
        }
    }
    return answer;
}