알고리즘/프로그래머스
프로그래머스 카펫 : 완전탐색 (C++)
개발하는 크롱
2020. 12. 28. 21:42
반응형
문제 링크: programmers.co.kr/learn/courses/30/lessons/42842
카펫의 가로 세로 길이를 구하는 문제이다.
가로 길이를 x, 세로 길이를 y라고 하자. 테두리 1줄이 갈색이고, 나머지 안쪽은 노란색이라고 했다.
네 변에 접한 타일(갈색 타일)의 개수는 양변의 길이를 두번씩 더하고 겹치는 모서리를 한번 빼준 값인 2x+2y-4이다.
안쪽의 타일(노란 타일)의 개수는 (x-2)*(y-2)이다.
갈색 타일과 노란색 타일을 더한 개수가 x*y임을 이용해서 푸는 문제이다.
반복문을 돌면서 조건에 맞는 x(가로 길이)를 찾았다.
총 타일 개수 x*y를 value라고 뒀다. 그렇기에 일단 반복문 내의 해당 iteration에서 value가 x로 나눠떨어지지 않는다면 조건에 불일치하므로 continue를 사용해 다음 x값을 테스트하도록 했다.
value가 x로 나눠 떨어진다면 위의 타일 개수 식을 활용해 점검한 후 조건에 맞으면 맞는 x와 y를 구한것으로 판단해 값을 리턴한다.
#include <string>
#include <vector>
#include <cstdio>
using namespace std;
vector<int> solution(int brown, int yellow) {
vector<int> answer;
int x, y; //x: answer[0], y: answer[1]
int value = brown + yellow;
//brown 개수: 2x + 2y - 4
//yellow개수: (x-2)*(y-2)
//brown + yellow: x*y
for(int x = 1 ; x < value ; x++){
if(value % x != 0) continue;
y = value / x;
if(brown == (2 * x + 2 * y - 4) && yellow == (x - 2) * (y - 2)){
answer.push_back(y);
answer.push_back(x);
return answer;
}
}
return answer;
}
반응형