<프로그래머스 C++> 카펫 풀이 (브루트포스)

문제

중앙은 "노란색", 테두리 1줄은 "갈색"인 격자 모양 카펫에서 갈색 격자 수 brown과 노랜삭 격자 수 yellow가 주어질 때, 카펫의 가로/세로 크기를 return하는 문제이다.

단, 가로 길이는 세로 길이보다 크거나 같다.

---

풀이 아이디어

가로를 w, 세로를 h라고 하면 두 가지 관계식을 세울 수 있다.

 

1. 전체 크기

w * h = brown + yellow

 

2. 갈색 테두리 수

테두리는 위 / 아래 / 좌 / 우 한 줄씩인데, 네 모서리는 중복으로 계산되기 때문에 4를 뺀다.

■ ■ ■ ■
■ □ □ ■
■ ■ ■ ■

위쪽:   w개
아래쪽: w개
왼쪽:   h개
오른쪽: h개
→ 2*w + 2*h - 4 (모서리 4개 중복 제거)

2*w + 2*h - 4 = brown

 

 

브루트포스

이 두 식을 연립해서 풀어도 가능하지만, 브루트포스 방식으로 접근하면 더 간단해진다.

 

w * h = total이므로, w와 h는 total의 약수의 쌍과 같다.

h를 1부터 늘려가면서 total %  == 0인 경우에 brown 조건을 체크하면 된다.

 

total = 12 (brown=10, yellow=2)

약수 쌍 탐색:
h=1: w=12  →  2*12+2*1-4=22  ≠ 10
h=2: w=6   →  2*6+2*2-4=12   ≠ 10
h=3: w=4   →  2*4+2*3-4=10   == 10  → [4, 3]

 

가로가 세로보다 크거나 같아야 하므로 w < h가 되는 순간 더 이상 탐색할 필요가 없다.

---

문제 풀이

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

vector<int> solution(int brown, int yellow) {
    vector<int> answer;
    int total = brown + yellow;

    for(int h = 1; h <= total; ++h)
    {
        if(total % h == 0)
        {
            int w = total / h;
            if(w < h) break;

            if(2*w + 2*h - 4 == brown)
            {
                answer = {w, h};
                break;
            }
        }
    }
    return answer;
}

---

코드 흐름

1. 전체 크기 계산

int total = brown + yellow;

 

전체 격자 수를 구한다.

w*h = total이므로 w와 h는 total의 약수의 쌍이다.

 

2. 약수 쌍 탐색

for(int h = 1; h <= total; ++h)
{
    if(total % h == 0)
    {
        int w = total / h;

 

h를 1부터 늘려가면서 total을 나누어 떨어지는 경우에만 처리한다(약수인 경우). 

나머지가 0이면 h가 약수이고, w = total / h로 가로길이를 구한다.

 

3. 가로 세로 조건

if(w < h) break;

 

 

문제 조건에서 가로가 세로보다 크거나 같아야 한다는 조건이 있었다. h가 커질수록 w는 작아지므로 w < h가 되는 순간 이후 약수 쌍은 모두 세로가 길어져 조건을 만족하지 않는다.

그 이후부터는 break로 탐색을 종료한다.

 

4. brown 조건 체크

if(2*w + 2*h - 4 == brown)
{
    answer = {w, h};
    break;
}

 

테두리 공식 2 * w + 2 * h - 4가 brown과 일치하게 되면 정답이다. {w, h} 순서로 반환한다.

---

핵심 포인트

 

• 테두리 갈색 수는 2 * w + 2 * h - 4로 표현된다
• w * h = total이므로 h의 약수 쌍을 브루트포스로 탐색한다
• w < h가 되는 순간 break해서 불필요한 탐색을 줄인다