문제 42842. 카펫

문제 링크

https://school.programmers.co.kr/learn/courses/30/lessons/42842

프로그래머스

 

 

난이도 : Lv.2 

 

문제 요약 설명

중앙에는 노란색으로 칠해져 있고 테두리 1줄은 갈색으로 칠해져 있는 격자 모양 카펫이 있습니다. 카펫의 가로, 세로 크기를 순서대로 배열에 담아 return 하도록 solution 함수를 작성해주세요.

입력

• 갈색 격자의 수 brown
• 노란색 격자의 수 yellow

입력 제한

• 갈색 격자의 수 brown은 8 이상 5,000 이하인 자연수입니다.
• 노란색 격자의 수 yellow는 1 이상 2,000,000 이하인 자연수입니다.
• 카펫의 가로 길이는 세로 길이와 같거나, 세로 길이보다 깁니다.

입력 예제

// input
10 // brown
2  // yellow

// ans
[4, 3]

 

풀이 방식

해당 문제는 브루트 포스(brute force)방법을 사용했다. 가로*세로 길이가 3*3인 카펫부터 시작해서 4*3, 4*4, 5*3, 5*4, 5*5...와 같은 패턴으로 매개변수로 입력받은 brown, yellow와 개수가 일치하는 카펫 크기를 찾는다. 만약 카펫 크기를 찾았다면 가로 세로 길이를 answer로 반환한다. 

 

+) 이렇게 풀어도 되는 이유는 brown의 개수 제한이 5000이기 때문이다. brown의 개수는 대충 가로+세로/2로 볼 수 있는데 즉, 가로 + 세로 <= 2500이기때문에 모든 가로 세로 조합을 다해봐도 시간초과 기준인 1억 번의 연산이 절대 나올 수 없다. 따라서 시간초과 걱정없이 이중 반복문으로 돌려도 된다.

 

정답 코드 

 

#include <string>
#include <vector>

using namespace std;

vector<int> solution(int brown, int yellow) {
    vector<int> answer;
    bool find = false;
    
    int height = 3, width = 3;
    int cur_brown, cur_yellow;
    while(!find){
        
        for(int h = 3; h <= width; h++){
            cur_brown = width*2 + h*2 - 4;
            cur_yellow = (width-2) * (h-2);
            
            if(cur_brown == brown && cur_yellow == yellow){
                height = h;
                answer = {width, height};
                find = true;
                break;
            }
        }
        if(find) break;
        
        width++;
    }
    
    
    
    return answer;
}