숨막히는 알고말고/문제 풀이
[Programmers] 카펫
숨숨숨
2020. 11. 10. 01:54
👀 문제 설명
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;
}