(C++) 프로그래머스 level2 : 카펫

문제 설명

 

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]
24	24	[8, 6]

 

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

---

풀이1

 

문제 유형은 완전탐색이었지만 굳이 특정한 알고리즘을 사용하지 않고도 해결할 수 있었다.

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

vector<int> solution(int brown, int yellow) {
    int h = 1; //세로
    int w = brown / 2 + 1; //가로
    while (h <= w) //가로의 길이가 세로의 길이보다 길거나 같은 동안
    {
        if ((h - 2) * (w - 2) == yellow) return { w,h };
        w--;
        h++;
    }
}

 

가로의 길이는 세로의 길이보다 길거나 같기 때문에 해당 조건이 만족하는 동안 while문을 돌려주었다.

가로의 길이 >= 세로의 길이 이기 때문에 세로의 길이를 처음에 1로 두고

1씩 늘려갔다. (가로의 길이는 1씩 감소)

그리고 카펫 조건을 만족시킬 때, 해당 가로,세로 길이를 return 해주었다.

 

 

풀이2- BFS

 

bfs로도 한번 풀어보았다

#include <iostream>
#include <queue>
#include <vector>
using namespace std;    

bool isAnswer(int w, int h, int brown, int yellow)
{
    if ((h - 2) * (w - 2) == yellow && 2 * (h + w - 2) == brown) return 1;
    return 0;
}

vector<int> solution(int brown, int yellow) {
    int h = 1; //세로
    int w = brown / 2 + 1; //가로
    queue<pair<int, int>>q; //{가로,세로}
    q.push({ w,h });
    while (!q.empty())
    {
        int nowW = q.front().first;
        int nowH = q.front().second;
        q.pop();
        if (isAnswer(nowW,nowH,brown,yellow)) return {nowW,nowH};
        q.push({ nowW - 1,nowH + 1 });
    }
}

 

그러나 이 문제에는 적합하지 않은 풀이인 것 같고, 처음 소개한 방식으로 해결하는것이 훨씬 효율적인 방법인 것 같다.