프로그래머스 카펫 C++

프로그래머스 : 카펫

프로그래머스

 

---

- 문제

  카펫이 주어지면 카펫의 x,y 크기를 구하는 문제다.

 

---

- 풀이

#include <string>
#include <vector>

using namespace std;

vector<int> solution(int brown, int yellow) {
    vector<int> answer;
    int all = brown + yellow;
    for(int i = 3; i < 2000; i++){
        for(int j = 3; i * j <= all;j++){
            if(i * j == all && (i*2 + j*2 - 4 == brown)){
                answer.push_back(j);
                answer.push_back(i);
                return answer;
            }
        }
    }
    return answer;
}

 

 

brown와 yellow를 합친게 결국 x * y가 될 것이고, brown은 바깥 테두리니깐 x * 2 + y * 2 - 4가 될 것이다.

 

그나마 시간복잡도를 줄이려고 이중반복문의 범위를 x * y가 더 작거나 같을때만 해당되도록 했다.

 

  

---

- 기억할 것!

 X