프로그래머스 - 카펫 #완전탐색

esc247·2022년 7월 17일
0

Algorithm

목록 보기
5/11

프로그래머스 - 카펫

출처

처음엔 brown 조건을 생각하지 않고,
yellow에 해당하는 수의 약수를 구한 후
곱했을 때 yellow수가 나오면서 차이가 최소인 한 쌍의 약수를 찾아 각각에 2를 더해주고 answer 벡터에 넣었다.

이렇게 한 이유는
주어진 예시와 내가 생각한 예시에서 모두 답이 되었기 때문인데,
조금 성급했다.
그렇다면 굳이 brown 값을 줄 이유가 없기 때문이다.
일반화를 늘 생각해야겠다.

바꾼 풀이는,
약수가 있는 벡터 중앙부터 바깥쪽으로 움직이며
(큰약수+작은약수)*2+4 값이 brwon과 같은지 확인했다.

#include <string>
#include <vector>
#include <cmath>
using namespace std;
vector<int> vec;
void func(int a){
    if(a<0) return;
    
    else{
        for(int i=1;i<=a;i++){
            if(a%i==0){
                vec.push_back(i);
            }
        }
    }
}
vector<int> solution(int brown, int yellow) {
    vector<int> answer;
    if(yellow==1){
        answer.push_back(3);
        answer.push_back(3);
        return answer;
    }
    func(yellow);
    
    if(vec.size()%2!=0){
        int mid = vec.size()/2;
        int tempa=0,tempb=0;
        for(int i=0;i<vec.size()/2;i++){
            tempa = vec[mid-i];
            tempb= vec[mid+i];
            int tempbrown = (tempa+tempb)*2 +4;
            if(tempbrown==brown)    break;
        }
        answer.push_back(tempa+2);
        answer.push_back(tempb+2);
    }else{
        int midf = vec.size()/2;
        int midb = vec.size()/2-1;
        int tempa=0,tempb=0;
        for(int i=0;i<vec.size()/2;i++){
            tempa = vec[midf+i];
            tempb = vec[midb-i];
            int tempbrown = (tempa+tempb)*2+4;
            if(tempbrown==brown)    break;
        }
        answer.push_back(tempa+2);
        answer.push_back(tempb+2);
    }
    
    return answer;
}
  • 다른 사람 풀이에서 배울 점:
    1. 가로와 세로 모두 무조건 3이상,
    2. 구해야 할 가로와 세로의 곱 == brown+yellow

이를 이용하면 반복문,조건문 쉽게 만들 수 있다.

  • 참고한 문법:
  1. cmath - sqrt
#include <cmath>
sqrt(double 제곱수)
  1. 약수 구하는 함수
    for문 i=1 부터 해당 수까지 % 값 0인지 아닌지 확인.
    (사실 약수를 구하는 대상의 수를 a라고 할때,
    a/2 까지 구해도 된다.)
profile
막상 하면 모르니까 일단 하자.

0개의 댓글