[프로그래머스] 카펫 C++ 풀이

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

프로그래머스

 

전체 코드

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

vector<int> solution(int brown, int yellow) {
    vector<int> answer;
    for(int i=3;;i++) //세로
    {
        for(int j=3;;j++) //가로
        {
            if(i*j>brown+yellow)
                break;
            else if((i-2)*(j-2)==yellow)
            {
                answer.push_back(j);
                answer.push_back(i);
                return answer;
            }
            
        }
    }
}

 

풀이 방법

3x3을 예로 들어보겠다.

 

Yellow 부분은 겉 테두리를 제외하고 꽉 채운다.

즉, 맨위 1칸과 맨아래 1칸을 빼버린것이 yellow 구역의 세로 길이가 된다.

이것은 가로 길이도 똑같이 적용된다.

 

그럼 이 원리는 4x3이든 4x4이든 동일하게 적용이 된다.

테두리만 제외하면 yellow 구역이 되니깐 전체 길이에서 맨위, 맨아래 즉, 양 사이드 블럭 2개를 빼버리면 yellow 구역의

한쪽 길이를 구할 수 있는것이다.

이런 방식으로 세로 길이와 가로 길이가 주어졌을때 우리는 yellow 구역의 넓이를 구할 수 있다.

 

그래서 yellow 구역의 넓이가 일치하는 카펫의 모양을 찾는것이 해법이다.

for(int i=3;;i++) //세로
{
	for(int j=3;;j++) //가로
    {
    	...
    }
}

for문은 세로와 가로 길이를 모두 탐색하게 만들었다.

i와 j가 3부터 시작인 이유는

문제 조건에서 brown은 8이상, yellow는 1이상이 최소값이므로

만족하는 최소크기의 카펫모양은 3x3이다.

그래서 가로 세로 길이를 3부터 시작한것이다.

 

if(i*j>brown+yellow)
	break;

카펫의 넓이는 brown+yellow를 넘어 설 수 없으니

이때 break하여 가로 길이의 반복문을 탈출하게 만들었다.

 

else if((i-2)*(j-2)==yellow)
{ ... }

세로 길이 i에서 2를 뺀 길이와 가로 길이 j에서 2를 뺸 길이를 곱하면

yellow 구역의 넓이가 되는데 이것이 yellow와 일치하면

찾던 카펫 모양을 찾은것이다.

 

yellow만 가지고 주어진 brown과 yellow를 만족시키는 카펫의 모양을 찾을 수 있을까 싶은데

찾을 수 있다. 그냥이 아니고 아래의 if문 덕분이다.

if(i*j>brown+yellow)
	break;

 

 

yellow가 24개인 카펫을 찾으려고 하는데 카펫의 모양은 여러개가 있다.

그중 두개만 들면

이런 모양인데 두개다 (i-2)(j-2)==yellow를 만족한다.

하지만 우리에게 주어진 yellow, brwon 블럭의 개수의 합은 i*j를 넘어갈 수 없기에

위의 if문에서 다 걸러져 만들 수 있는 사각형만 걸러져 나온다.