프로그래머스 - 카펫 / C++

문제 링크 : https://programmers.co.kr/learn/courses/30/lessons/42842#

코딩테스트 연습 - 카펫

 

 

문제 풀이

문제를 읽고 테스트케이스를 보니 제일 먼저 떠오른 수식은

yellow + brown = w * h이다. 바로 구현하여 브루트포스하였지만 테스트케이스 4, 6, 7을 통과하지 못했다.

 

검색해보니 반례가 brown = 18, yellow = 6인 경우 그림과 같이 만들려면 width = 8, height= 3이어야 하지만 width = 6, height = 4인 것도 수식에 일치하기 때문에 오답이 발생하였다.

 

그림과 같이 카펫을 만들기 위해서는 (width - 2) * (height - 2) == yellow가 되어야 하므로 첫 번째 수식을 test1 함수로 만들고,  해당 수식도 test2 함수로 만든 뒤 브루트포스 하였다.

 

소스 코드

#include <bits/stdc++.h>
using namespace std;

bool test1(int brown, int yellow, int w, int h){
    if(w*h == brown+yellow) return true;
    else return false;
}

bool test2(int yellow, int w, int h){
    if ((w-2) * (h-2) == yellow) return true;
    else return false;
}

vector<int> solution(int brown, int yellow) {
    vector<int> answer;
    bool flag = false;
    
    for(int i=0; i<5001; i++){ //i가 가로 크기
        for(int j=0; j<2000001; j++){ //j가 세로 크기
            if(test1(brown, yellow, i, j) && test2(yellow, i, j) && i >= j){
                answer.push_back(i);
                answer.push_back(j);
                flag = true;
                break;
            }
        }
        if(flag) break;
    }
    return answer;
}