[프로그래머스] 카펫 - 완전탐색 (C++) lv2

C++ 연습!

 

카펫의 가운데는 노란색, 테두리 1줄은 갈색

갈색과 노란색의 cell 개수만 보고 카펫의 가로, 세로 크기를 알 수 있을까?

 

아이디어: 노란색의 가로+2 = 갈색 가로, 노란색 세로+2 = 갈색 세로

 

총 cell 개수 = 노랑+갈색;

 

brown 가로세로 = 카펫 가로세로임

그러면 brown의 가로세로를 순차적으로 점검하며 possibility를 분석하면 된다

 

brown 세로 길이 최솟값 = 3

왜냐면 yellow의 최소 세로가 1임. 그리고 위아래로 brown cell이 1개씩 붙으니까 3

 

brown 세로 길이 최대 = 루트(총 cell 개수)

왜냐면 총 개수를 어떻게 구겨넣든 일단 가로=세로가 되는 지점에서 멈춰야 되니까

(그 이상으로 넘어가면, 그 이전에서 살펴본 것을 가로, 세로 길이만 바꿔서 다시 살펴보는 셈이 된다)

 

따라서 위 값 범주 사이에서 아래와 같은 조건을 살펴본다

 

만약 total%h==0인 경우, 세로 값으로 가로 값이 나누어 떨어져 직사각형이 형성 가능한 경우

세로 값을 바탕으로 가로 값을 total/h로 설정해준다

 

그리고 이 값을 바탕으로 yellow 값이 유효한지 봐줄건데,

brown은 너비가 1인 테두리이기 때문에 yellow에서 좌우 또는 상하 1씩 더해서

각 가로 세로값에서 yellow+2=brown이 된다

 

따라서, (w-2)*(h-2) 값이 yellow와 같은지 비교하고,

참이면 각 값을 가로-세로 순으로 answer 배열에 push_back한 후 break;

*push_back은 벡터 끝에 새로운 원소를 추가하는 방법이다.

 

#include <string>
#include <vector>
#include <cmath>
#include <iostream>

using namespace std;

vector<int> solution(int brown, int yellow) {
    vector<int> answer;
    int total = brown+yellow;
    
    for(int h=3; h<=sqrt(total);h++){
        if(total%h==0){
            int w = total/h;
            if((w-2)*(h-2)==yellow){
                answer.push_back(w);
                answer.push_back(h);
                break;
            }
        }
    }
    return answer;
}

 

 

번외

이건 그냥 궁금해서 삽질해본건데

결과는 이상한 값이 나와서 완전탐색으로 얌전히 풀었다

(gpt한테 어떻게 가능하게 안될까? 했다가 님아 이문제 이런 식으로 푸는거 아님;;하고 혼남)

ㄴ 이렇게 풀지 마세용

 

 

작성 시작: 11.06 11:52

작성 종료: 11.06. 12:31

 

밥먹으러 가야지!!

오늘 학식 특식이 아직 안끝났을까!?!?!