[프로그래머스 lv2] 카펫 풀이

✅ 프로그래머스의 모든 문제와 해설 보기[클릭]

 

해설

brown 카펫은 yellow 카펫들을 둘러싸고 있는 '한 층의' 테두리이다.

따라서 brown 카펫 수를 통해 가로와 세로 길이 합(s)을 구할 수 있다.

 

출처: 프로그래머스

 

가로의 길이가 a, 세로의 길이가 b, s = a+b라 하자.

전체 테두리 길이 brown은 a*2 + (b-2)*2 이므로, 

2*a+2*b-4 = brown

2*(a+b) = brown+4

a+b = (brown+4)/2 

s = (brown+4)/2 가 된다.

 

가로와 세로 길이의 합을 알고 있으므로, 가로의 길이를 결정하면 세로의 길이를 바로 구할 수 있다.

가로는 세로보다 길어야 하므로, 가로는 (s+1)/2 (s를 2로 나눈 몫의 올림) 이상이어야 한다.

 

가로는 최소 세로 길이를 남겨야 하는데, 하나 이상의 노란 카펫을 감싸기 위해서는 세로의 길이가 최소 3 이상이어야 한다.

따라서 가로는 s-3 이하이어야 한다. 

 

가로의 범위를 모두 탐색하면서 세로를 결정하고, 

이 때의 노란 카펫 개수가 문제에서 주어진 yellow와 같으면 가로와 세로 값을 리턴한다.

 

 

코드

 

#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <tuple>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <iostream>

using namespace std;
using ii = pair<int, int>;
using iii = tuple<int, int, int>;

#define X first
#define Y second

vector<int> solution(int brown, int yellow) {
    
    int s = (brown+4)/2;
    int st = (s+1)/2;
    int en = s-3;
    for (int w=st; w<=en; w++) {
        int h = s-w;
        if ((w-2)*(h-2) == yellow) return {w, h};
    }
    return {-1, -1};
}