[프로그래머스] 카펫

▶문제설명

코딩테스트 연습 > 완전탐색 > 카펫

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

▶ 설계

---

brown와 red의 값에 따라서 카펫의 가로, 세로 크기를 리턴해야 하는 함수이다.

단순히 가능한 가로, 세로의 길이를 2중 for문으로 완전탐색하면 풀릴 것으로 보인다.

▶ 구현

---

우선 2중 for문으로 가능한 가로, 세로 길이를 모두 탐색하도록 하자.

vector<int> solution(int brown, int red) {
    vector<int> answer;
    for(int w=1; w<=5000 ; w++){
        for(int h=1; h<=5000; h++){
            
        }
    }
    return answer;
}

brown의 최대 값이 5000이라고 주어졌다.

그래서 넉넉하게 1부터 5000까지 반복하도록 구현했다. brown이 테두리 영역의 크기이므로 당연히 가로, 세로의 길이가 5000이 되는 일은 없다.

vector<int> solution(int brown, int red) {
    vector<int> answer;
    for(int w=1; w<=5000 ; w++){
        for(int h=1; h<=5000; h++){
            if(w < h)   break;
 
        }
    }
    return answer;
}

가로의 길이 >= 세로의 길이라고 주어졌으므로 세로의 길이가 더 긴 경우는 제외하도록 구현했다.

이제 핵심이 되는 부분이다. 

가로의 길이와 세로의 길이에 따라서 brown, red의 값을 구해서 같은지 비교해보아야 한다.

vector<int> solution(int brown, int red) {
    vector<int> answer;
    for(int w=1; w<=5000 ; w++){
        for(int h=1; h<=5000; h++){
            if(w < h)   break;
            if(brown == w*2+h*2-4 && red == w*h-brown){
                answer.push_back(w);
                answer.push_back(h);
                return answer;
            }
        }
    }
    return answer;
}

red 값을 구하기 위해서는 사각형의 넓이에서 테두리 영역만 제외하면 되므로 brown 값만 구하면 쉽게 구할 수 있다.

brown 값을 구하는 데 어떻게 저런 수식이 나왔을까?

나무상자가 여러개 있다고 가정해보자.

그리고 머릿속에 그림을 그려보자.

사각형의 윗 변을 나타내기 위해 w개의 상자를 가로로 차례대로 놓았다.

그리고 아랫 변을 나타내기 위해 밑변이 될 지점에 w개의 상자를 가로로 차례대로 놓았다.

이제 왼쪽 변과 오른쪽 변을 나타내기 위해 해당하는 위치에 h개씩 놓아보자.

그러면 네 곳의 꼭지점에 상자가 2층으로 놓여지게 된다.

즉, 테두리를 나타내는데 4개의 상자는 필요없다는 말이 된다.

▶ 결과

---

▶Solution

---

[소스코드 보기]