[프로그래머스/Level 2] 카펫 (C++)

programmers.co.kr/learn/courses/30/lessons/42842

코딩테스트 연습 - 카펫

 

처음에 접근했을 때는 가로 세로의 길이가 갈색, 노란색 격자의 합의 약수 관계라는 규칙을 발견했고, 세로가 가로의 길이보다 같거나 작으므로 세로에 격자의 합의 제곱근 길이를 넣은 후, 합에서 세로를 나눠 가로를 구하였다.

그러나 위의 방법같은 경우 노란색 격자가 6개인 경우 문제점이 발생한다. 노란색 격자가 6개일 때, 다음과 같이 카펫이 위치할 수 있기 때문이다.

 

BBBBBBBB

BYYYYYYB

BBBBBBBB

 

따라서 다른 방법으로 접근을 해야하는데 다음과 같이 문제를 해결할 수 있다.

 

1. 세로를 3(노란색 격자 1개와 위 아래 빨간색 격자 하나씩)에서 부터 격자 합의 제곱근까지 반복문
2. 합에서 세로를 나누어 가로를 구하고, 각각에 2를 빼어 곱한 값이 노란색 격자의 수와 같은지 비교
   -같으면 종료 후, 가로 세로 값을 벡터에 넣어줌

 

#include <string>
#include <vector>
#include <cmath>
using namespace std;

vector<int> solution(int brown, int yellow) {
    vector<int> answer;
    int w, h;
    int sum = brown + yellow;
    
    for(int h = 3; h <= sqrt(sum); h++) {
        int w = sum / h;
        if((w - 2) * (h - 2) == yellow) {
            answer.push_back(w);
            answer.push_back(h);
            return answer;
        }
    }
}