프로그래머스lv2-카펫

다음은 프로그래머스-카펫에 대한 문제풀이다.

매개변수로 brown과 yellow의 타일 갯수가 주어지면 전체 카펫의 너비와 높이를 반환하면 되는 문제다.

 

처음엔 타일의 갯수와 결과 값에 대응되는 점화식이 존재할 거라 생각해 다이나믹 프로그래밍으로 방식으로 접근했지만 점화식 문제가 아니었다. 우선 yellow의 수가 정해지면 나올 수 있는 yellow의 모양은 약수를 기반으로 정해진다. Yellow 수각 4라면 Yellow 모양은 1X4, 2X2가 나올 수 있고 거기에 대응되는 brown 타일의 수는 14개와 12개다. 매개변수도 brown 수도 입력으로 주어지므로 매개변수 값과 동일한 brown 타일 수를 갖는 yellow타일의 모양을 고른다. 그리고 yellow타일이 어떤 모양으로 정해진지 알면 전체 너비와 높이도 계산 할 수 있다. yellow모양이 1X4로 정해지면 1 + 2, 4 + 2로 너비와 높이를 알 수 있다. 그리고 문제에서 가로가 세로보다 같거나 크다고 하였으므로 최종적으론 4, 3이 정답이 된다.

 

#include <string>
#include <vector>

using namespace std;

int calcBrown(int row, int col) {

    return 2 * row + 2 * col + 4;
}

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

    for (int i = 1; i <= yellow; i++) {
        if (yellow % i == 0) {
            int yr = i, yc = yellow / i;
            int b = calcBrown(yr, yc);

            if (b == brown) {
                int width = yr + 2;
                int height = yc + 2;

                if (width >= height) {
                    answer.push_back(width);
                    answer.push_back(height);
                }
                else {
                    answer.push_back(height);
                    answer.push_back(width);
                }
                break;
            }
        }
    }

    return answer;
}

위의 코드를 설명하면 약수를 기반으로 yellow의 모양을 찾는다.

전체 카펫의 너비와 높이를 계산해서 반환한다.

 

참고

프로그래머스