[C++] 프로그래머스 : 카펫

출처: 프로그래머스 코딩테스트 연습,https://school.programmers.co.kr/learn/courses/30/lessons/42842

프로그래머스

 

[문제 풀이]
1. yellow의 면적에서 만들 수 있는 모든 직사각형을 완전탐색하면 해결이 가능하다.

2. 예를들어 yellow가 24일때 만들 수 있는 직사각형의 {가로,세로} 쌍은 {24,1} ,{12,2},{8,3} .... 이런식이다.

3. yellow의 가로는 세로의 길이보다 늘 크거나 같으므로 {4,6} 같은 경우의수는 고려할 필요가 없다.

4. 가로,세로 쌍을 찾을 때에는 yellow의 약수를 구하는 알고리즘을 사용하면 된다.

5. yellow의 면적은 최대 2,000,000 이므로 , yellow를 1에서 2000000으로 모두 나누면서 약수를 구하면 시간에서 불리하다.

6. yellow를 1이 아닌 루트(yellow) 까지만 나누어도, 모든 경우의 수를 알 수 있다.

7. 루트(2000000)은 정말 대충 계산해도 1000과 2000 사이이다. 완전탐색 가능.

 

8. yellow의 가로와 세로가 A,B 일때, 필요한 brown 타일 수는 2A+2B+4 이다. 이것이 brown과 같다면 이 경우의 수 가 정답이다.

9. A와 B에 각각 2를 더해주면 문제에서 요구하는 가로와 세로길이이다.

[C++ Code]

#include <string>
#include <vector>

using namespace std;

vector<int> solution(int brown, int yellow) {
    vector<int> answer;
    int A; // 노랑 가로
    int B; // 노랑 세로
    int temp_brown; // 임시로 연산한 갈색타일 개수
    
    //yellow의 약수 쌍들을 완전탐색하면 된다.
    for (int i = 1 ; i*i <= yellow ; i++){
        if(yellow % i != 0) continue; // 나누어 떨어지지 않는 경우는 버린다.
        A = yellow/i; //가로의 길이가 항상 세로보다 길거나 같다.
        B = i;
        temp_brown = 2*A + 2*B + 4;
        if(temp_brown == brown){
            answer = {A+2, B+2};
            break;
        }
    }
    
    return answer;
}