https://programmers.co.kr/learn/courses/30/lessons/42842?language=cpp 

 

코딩테스트 연습 - 카펫

Leo는 카펫을 사러 갔다가 아래 그림과 같이 중앙에는 노란색으로 칠해져 있고 테두리 1줄은 갈색으로 칠해져 있는 격자 모양 카펫을 봤습니다. Leo는 집으로 돌아와서 아까 본 카펫의 노란색과

programmers.co.kr

 

분명 일주일 전에 처음 봤을 때에는 '오잉? 이걸 어떻게 풀지?' 하고 미뤄뒀다가 일주일 후에 보니

'뭐야? 브루트 포스로 하면 쉽겠는데?'라는 생각이 들어 신기했던 문제.

근데 단순 브루트 포스라고 하기엔 규칙이 하나 더 있음.

 

일단 brown + yellow 가 가로 * 세로 여야 한다는 것이 제일 먼저 눈에 띈 규칙이었고,

이 규칙만으로는 3 개의 테스트케이스를 통과하지 못해서 추가로 알아낸 것이

가로 - 2 * 세로 - 2 가 yellow의 값과 같아야 한다는 것.

브루트포스 유형이라고 나와 있으므로 for문의 최대값은 사실 무한이라고 봐도 될 정도로 크게 줌.

아래는 정답 코드.

 

 

#include <string>
#include <vector>

using namespace std;

vector<int> solution(int brown, int yellow) {
    vector<int> answer;
    long long target = brown + yellow;
    
    for (long long horizontal = 3; horizontal <= 2000000; horizontal++)
    {
        for (long long vertical = 3; vertical <= horizontal; vertical++)
        {
            if (horizontal * vertical == target && 
            	((horizontal - 2) * (vertical - 2) == yellow)) 
            {
                answer.push_back(horizontal);
                answer.push_back(vertical);
                return answer;
            }
        }
    }
    return answer;
}
  • 네이버 블러그 공유하기
  • 네이버 밴드에 공유하기
  • 페이스북 공유하기
  • 카카오스토리 공유하기
// custom