[프로그래머스/level2/c++] 카펫-"완전탐색"

문제 :

Leo는 카펫을 사러 갔다가 아래 그림과 같이 중앙에는 노란색으로 칠해져 있고 테두리 1줄은 갈색으로 칠해져 있는 격자 모양 카펫을 봤습니다.

Leo는 집으로 돌아와서 아까 본 카펫의 노란색과 갈색으로 색칠된 격자의 개수는 기억했지만, 전체 카펫의 크기는 기억하지 못했습니다.

Leo가 본 카펫에서 갈색 격자의 수 brown, 노란색 격자의 수 yellow가 매개변수로 주어질 때 카펫의 가로, 세로 크기를 순서대로 배열에 담아 return 하도록 solution 함수를 작성해주세요.

 

제한 사항 :

• 갈색 격자의 수 brown은 8 이상 5,000 이하인 자연수입니다.
• 노란색 격자의 수 yellow는 1 이상 2,000,000 이하인 자연수입니다.
• 카펫의 가로 길이는 세로 길이와 같거나, 세로 길이보다 깁니다.

입출력 예 :

brown	yellow	return
10	2	[4,3]
8	1	[3,3]
1	24	[8,6]

 

코드 :

#include <string>
#include <vector>

using namespace std;

vector<int> solution(int brown, int yellow) {
    vector<int> answer(2);  //초기화
    int yellow_w;
    for(int i=1;i<=yellow;i++){
        if(yellow%i==0){
            yellow_w=yellow/i;
            if(i+yellow_w==-(brown-4)/2 || i+yellow_w==(brown-4)/2){
                answer[0]=yellow_w+2;  //w
                answer[1]=i+2;        //h
                return answer;
            }
        }
    }
}

 

다시 한번 짚고 넘어가기 :

-수학공식을 세워서 문제에 접근해보았다.

 yellow의 width과 height를 중점적으로 식을 세웠다.

 yellow_w*yellow_h=yellow이기 때문에

 (yellow_w)*2 + (yellow / yellow_w )*2 =brown이고

 yellow_w^2 -(brown-4)/2yellow_w+yellow=0이므로 11번째 줄의 if문이 나온것이다.

 for문은 1부터 시작하기 때문에 i값은 yellow_w보다 작은 수이므로 answer[1]에 할당하였고 yellow의 w,h값이므로 +2를 하였다.

 

- 다른 답 :

#include <string>
#include <vector>

using namespace std;

vector<int> solution(int brown, int yellow) {

    int len = brown / 2 + 2;

    int w = len - 3;
    int h = 3;

    while(w >= h){
        if(w * h == (brown + yellow)) break;

        w--;
        h++;
    }

    return vector<int>{w, h};
}

 

카펫의 w와 h를 기준으로 세운식으로

w * h = brown + red, (w-2) * (h-2) = red, 두 식을 red를 대입해서 연립방정식을 이용한 풀이이다.

더 깔끔한 풀이인것 같다.

출처 : 프로그래머스 >다른 사람의 풀이

 

도움이 된 글 :

완전탐색의 종류를 알아보았다.

• 브루트 포스 : for문을 이용하여 처음부터 끝까지 탐색하는 방법
• 비트 마스크 : 이진수 표현을 자료구조로 쓰는 기법 (AND, OR, XOR, SHIFT, NOT)
• 백트래킹 : 분할정복을 이용한 기법, 재귀함수를 이용, 해를 찾아가는 도중에 해가 될 것 같지 않은 경로가 있다면 더 이상 가지 않고 되돌아간다.
• 재귀함수 : 함수 내에서 함수 자기 자신을 계속해서 호출하는 것
• 순열 : 서로 다른 n개의 원소에서 r개의 중복을 허용하지 않고 순서대로 늘어 놓은 수
• BFS(너비 우선 탐색)
• DFS(깊이 우선 탐색)

developmentnotepad.tistory.com/entry/Algorithm-%EC%99%84%EC%A0%84%ED%83%90%EC%83%89-%EB%B8%8C%EB%A3%A8%ED%8A%B8-%ED%8F%AC%EC%8A%A4-Exhaustive-Search

[Algorithm] 완전탐색 (Exhaustive Search)