https://programmers.co.kr/learn/courses/30/lessons/42842
코딩테스트 연습 - 카펫
Leo는 카펫을 사러 갔다가 아래 그림과 같이 중앙에는 노란색으로 칠해져 있고 테두리 1줄은 갈색으로 칠해져 있는 격자 모양 카펫을 봤습니다. Leo는 집으로 돌아와서 아까 본 카펫의 노란색과
programmers.co.kr
격자의 가로가 세로보다 길거나 같다는 점을 이용해 탐색할 첫 가로의 길이를 격자 수의 제곱근의 천장함수로 잡아 완전탐색하였다.
소스코드
#include <string>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;
int length;
bool cmp(int a, int b) {return a > b;}
vector<int> solution(int brown, int yellow) {
vector<int> answer;
//전체 격자 개수
int all = brown + yellow;
//가로는 세로보다 크거나 같다는 점을 반영, -1은 반복문의 첫 문장 width++를 위해서 미리 하나 지워줌.
int width = ceil(sqrt(yellow))-1;
while(width <= yellow ) {
width++;
//약수가 아니면 다음 루프로 이동
if(yellow%width !=0) continue;
length = yellow / width;
//전체 격자의 가로와 세로는 노란격자의 가로와 세로보다 2씩 크다는 성질을 이용해 격자 개수 비교하기
if((width+2)*(length+2) == all) {
answer.push_back(width+2);
answer.push_back(length+2);
break;
}
}
return answer;
}
'CodingTest Practice > Programmers' 카테고리의 다른 글
프로그래머스 : 여행경로 (C++, Lv.3, DFS) (1) | 2022.05.27 |
---|---|
프로그래머스 : 단어변환(C++, Lv.3, BFS) (0) | 2022.05.27 |
프로그래머스 : 체육복 (C++, Lv.1, 탐욕법) (0) | 2022.05.22 |
프로그래머스 : 가장 큰 수 (C++, Lv.2,정렬) (0) | 2022.05.21 |
프로그래머스 : 전화번호 목록 (C++, Lv.2, 해시) (0) | 2022.05.20 |