[Programmers] 카펫

👀 문제 설명

문제

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]

✍🏻풀이

brown과 yellow, 그리고 carpet의 연관성을 생각하면 간단히 풀 수 있는 문제였다.

카펫의 격자 수는 brown + yellow이고,

카펫의 세로는 yellow의 세로 + 2, 가로는 yellow의 가로 + 2이다.

이 연관성을 생각하며 문제를 푸니 금방 풀 수 있었다.

 

코드

//
//  Programmers_42842.cpp
//  Algorithm
//
//  Created by 조수민 on 2020/10/28.
//  Copyright © 2020 조수민. All rights reserved.
//
//  카펫(https://programmers.co.kr/learn/courses/30/lessons/42842)

#include <stdio.h>
#include <iostream>
#include <string>
#include <vector>

using namespace std;

int carpetWidth = 0;
int carpetHeight = 0;

/**
 카펫의 가로를 carpetWidth, 세로를 carpetHeight라고 선언한다.
 노란색의 가로를 yellowWidth, 세로를 yellowHeight라고 선언한다.
 carpetWidth는 무조건 yellowWidth + 2가 된다. (감싸야 하므로)
 carpetHeight또한 carpetHeight + 2가 된다.
 carpet의 전체 격자 수는 yellow + brown이다.
 */
vector<int> solution(int brown, int yellow) {
    vector<int> answer;
    
    int carpet = brown + yellow;
    
    for (int yellowWidth = 1; yellowWidth <= yellow; yellowWidth++) {
        if ((yellow % yellowWidth) != 0) // yellow가 yellowWidth로 떨어지지 않으면
            continue; // 다음으로 넘긴다. (yellowWidth는 무조건 yellow의 약수여야 함)
        
        // yellowWidth가 yellow의 약수인 경우
        int yellowHeight = yellow / yellowWidth; // yellowHeight는 yellow / yellowWidth이고
        carpetWidth = yellowWidth + 2; // carpetWidth는 무조건 yellowWidth + 2이다.
        
        if ((carpet % carpetWidth) != 0) // 만약 carpet이 carpetWidth로 나누어 떨어지지 않으면 다음으로 넘긴다.
            continue;
        
        // carpetWidth가 carpet의 약수인 경우
        carpetHeight = carpet / carpetWidth; // carpetHeight는 carpet / carpetWidth이고
        if (carpetHeight == yellowHeight + 2) { // carpetHeight가 yellowHeight + 2이면 맞게 구한 것
            break;
        }
    }
    
    if (carpetWidth != 0 && carpetHeight != 0) {
        answer.push_back(carpetHeight);
        answer.push_back(carpetWidth);
    }
    
    return answer;
}

int main() {
    vector<int> sol = solution(24, 24);
    
    for (int i = 0; i < sol.size(); i++) {
        cout << sol.at(i) << " ";
    }
    
    return 0;
}