[프로그래머스/CPP/JS] 카펫
13846 단어 psbrute forceprogrammersbrute force
프로그래머스. 카펫
1. 문제
Leo는 카펫을 사러 갔다가 아래 그림과 같이 중앙에는 노란색으로 칠해져 있고 테두리 1줄은 갈색으로 칠해져 있는 격자 모양 카펫을 봤습니다.
Leo는 집으로 돌아와서 아까 본 카펫의 노란색과 갈색으로 색칠된 격자의 개수는 기억했지만, 전체 카펫의 크기는 기억하지 못했습니다.
Leo가 본 카펫에서 갈색 격자의 수 brown, 노란색 격자의 수 yellow가 매개변수로 주어질 때 카펫의 가로, 세로 크기를 순서대로 배열에 담아 return 하도록 solution 함수를 작성해주세요.
2. 제한사항
- 갈색 격자의 수 brown은 8 이상 5,000 이하인 자연수입니다.
- 노란색 격자의 수 yellow는 1 이상 2,000,000 이하인 자연수입니다.
- 카펫의 가로 길이는 세로 길이와 같거나, 세로 길이보다 깁니다.
3. 풀이
- yellow의 가로가
m
이고 세로가n
이면 brown의 개수는2(m+n+2)
다. 이와 일치하는 m과 n을 찾고 전체 가로의 길이는m+2
세로의 길이는n+2
로 구하면 된다. - yellow의
가로 +1
세로 +1
을 해보면서 가로와 세로가 증가할 때 brown의 가로와 세로가 어떻게 바뀌는 지 살펴보고 brown의 개수는2(m+n+2)
라는 결론을 내렸다. - m과 n의 후보를 찾기 위해 yellow의 약수를 찾는 함수를 만들었다. 약수는 짝이기 때문에 절반만 찾아주고 나머지 쌍은 실제로 계산할 때 처리해주었다.
4. 처음 코드와 달라진 점
- 약수 찾기에서 loop를 0부터 시작해서 0으로 나누는 오류로 발생했다.
- loop 시작을 1로 수정해주었다.
- 근데 loop 범위를 n/2까지로 하니까 1이 그냥 통과하더라
- 그래서 1은 모든 수 의 약수라서 loop 시작 전에 1은 미리 넣고 loop 시작을 2부터 범위를 n/2까지로 했다.
- 근데 테스트 케이스 한 개를 통과 못 하길래 n/2를 포함하게 바꿨더니 됐다
- 다 풀고 왜 그런가 생각해보니까
4의 경우
n/2를 포함 안 하게 되면 2가 약수로 안 들어간다.
5. 코드
#include <string>
#include <vector>
using namespace std;
vector<int> find_factor(int n){
vector<int> factors;
factors.push_back(1);
for(int i=2; i<=n/2; i++){
if(n % i == 0) factors.push_back(i);
}
return factors;
}
vector<int> solution(int brown, int yellow) {
vector<int> answer;
vector<int> factors = find_factor(yellow);
for(int factor : factors){
int divided = yellow / factor;
int result = (factor + divided + 2) *2;
if(result == brown) {
answer.push_back(divided+2);
answer.push_back(factor+2);
break;
}
}
return answer;
}
근데 이 문제 1점밖에 안준다...
➕ 21.09.01 추가
6. 풀이
brown = 2(m + n -2)
yellow = (m - 2)(n - 2)
- 1부터 2501까지 모든 경우를 조사했다.
- 2501까지인 이유
- brown ≤ 5000
- 2(m + n - 2) ≤ 5000
- m + n - 2 ≤ 2500
- m + n ≤ 2502
- m이 n보다 크다.
그래도 n이 1은 되겠지
- n은 m보다 작거나 같기 때문에 반복을 i와 같거나 같을 때까지만 한다.
- m을 i로 n을 j로 모든 경우를 조사하며 조건에 충족하면
answer
배열에 추가하고 반복을 종료한다.
7. 코드
#include <string>
#include <vector>
using namespace std;
vector<int> solution(int brown, int yellow) {
vector<int> answer;
for (int i = 1; i < 2502; ++i) {
for (int j = 1; j <= i; ++j) {
bool isBrown = 2 * i + 2 * j == brown + 4;
bool isYellow = (i - 2) * (j - 2) == yellow;
if (isBrown && isYellow) {
answer.push_back(i);
answer.push_back(j);
break;
}
}
}
return answer;
}
8. 코드(JS)
function solution(brown, yellow) {
const total = brown + yellow;
for (let height = 1; height < total; height++) {
const width = total / height;
if (width !== Math.floor(width)) continue;
if ((width - 2) * (height - 2) === yellow) return [width, height];
}
}
Author And Source
이 문제에 관하여([프로그래머스/CPP/JS] 카펫), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@e7838752/programmers42842저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)