[C++] 프로그래머스 카펫 문제풀이 코드 (완전탐색)

프로그래머스 코딩테스트 연습 완전탐색 카테고리의 카펫 문제를 풀었다.

문제 바로가기: https://programmers.co.kr/learn/courses/30/lessons/42842

(저의 풀이가 최적의 정답이 아닐 수 있고, 완벽하지 않을 수 있으니 간단한 참고 정도만 해주시길 바랍니다.)

 

문제를 읽은 후 연립 방정식이 세워봤다.

빨간색 격자의 가로 길이를 x, 세로 길이를 y라 했을 때

• brown = 2 ( x + y ) + 4
• red = x * y

이렇게 두가지 식이 세워졌고, 반환해야 하는 리턴값은 카펫의 가로와 세로 길이 이므로

x + 2, y + 2 를 각각 카펫의 가로, 세로 길이로 반환해주면 된다.

 

이 두가지 식을 가지고 완전 탐색으로 풀었다.

문제의 제한사항에서 brown의 범위는 8이상 5000이하인 자연수라 했으니

brown 이 최대인 5000이라 가정하면 x와 y는 많아봐야 2500 미만이다.

이를 각각 for문의 범위 제한 조건으로 문제를 풀었더니 모든 테케를 통과하였다.

그러나 왠지 너무 주먹구구식이라 최적의 풀이가 아닌 것 같아 찝찝하다..

 

#include <string>
#include <vector>
#include <iostream>
using namespace std;

vector<int> solution(int brown, int red) {
    vector<int> answer;
    
    for(int y = 1; y < 2500; y++) {
        for(int x = 1; x < 2500; x++) {
            if((brown - 4) / 2 == x + y && red == x * y) {
                if (x >= y) {
                    answer.push_back(x + 2);
                    answer.push_back(y + 2);
                    return answer;
                } else {
                    answer.push_back(y + 2);
                    answer.push_back(x + 2);
                    return answer;
                }
            }
        }
    }
    return answer;
}