프로그래머스 | 카펫

 

패턴이 분명 있을건데

노란색 기준으로 둘러싸고 있는 갈색의 개수를 찾아보면

노란색 24개 기준으로!

yellow	가로	세로	갈색 가로	갈색세로	도합	비고
24	24	1	24*2 = 48	(1+2) *2 = 6	54	X
24	12	2	12*2 = 24	(2+2)*2 = 8	32	X
24	8	3	8*2 = 16	(3+2)*2 = 10	26	X
24	6	4	6*2 = 12	(4+2)*2 = 12	24	O

 

이런식으로 찾아볼 수 있겠음!

노란색이 나누어떨어지는 수로 찾아서 brown 개수 구하고, 제시된거랑 똑같은거 나올때까지!

 

근데 생각해보니까 조건에서 yellow는 2,000,000 이하인 자연수이고

brown은 5,000 이하인 자연수니까 이걸 brown기준으로 해서 yellow를 찾는게 더 효율적인게 아닐까?

 

brown 세로	brown 가로	yellow 구하기
3(yellow 세로 1 기준) 점점 ++해가면서 찾기	전체/2 - 세로	가로 * (세로-2)

 

이런식으로 해서 구하면

갈색개수	갈색세로	계산	갈색가로	계산	노랑 개수	비고
24	3	12-3	9	(3-2)*9	9	9 != 24
24	4	12-4	8	(4-2)*8	16	16 != 24
24	5	12-5	7	(5-2)*7	21	21 != 24
24	6	12-6	6	(6-2)*6	24	24 == 24

 

숫자가 커질수록 이게 더 나은것 같다. 수 하나하나 나누어떨어지는지 비교 안해도 되고

#include <iostream>
#include <vector>
using namespace std;

vector<int> solution(int brown, int yellow) {
    vector<int> ans = {0,3};
    while(1){
        ans[0] = brown/2 - ans[1];
        if(ans[0]*(ans[1]-2) == yellow) break;
        ans[1]++;
    }
    ans[0] += 2;
    return ans;
}

생각보다 너무 쉽게 풀렸는디..?