[level 2] 카펫

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

 

첫 번째 방법

#include <string>
#include <vector>

using namespace std;

vector<int> solution(int brown, int yellow) {
    vector<int> answer;
    int br = (brown +4)/2;
    for(int y = 3,x= br-y; y < br && x>=3; y++){
        x = br-y;
        if(  (y-2)* (x-2) == yellow){
            answer.push_back(x);
            answer.push_back(y);
            break;
        }
    }
    return answer;
}

 

풀이 방법

문제의 제한 사항을 보니 brown의 범위가 yellow 보다 작아서 brown 기준으로 문제를 풀었다.

brown의 x,y가 될 수 있는 것 중 곱했을 때 yellow가 나오는 쌍을 찾았다.

 

 

2단계 치고 쉬운 문제였다.

다른 사람들의 풀이도 나와 크게 다르지 않았다.

 

 

복잡도 계산해보기

시간 복잡도 : 브라운을 n이라 할 때 더해서 n을 만들 수 있는 조합으로 for문을 돌리니까 O(n)

전체 넓이가 n이라하면 모르겠다.