[프로그래머스 Lv.2] 카펫

문제는 다음과 같습니다.

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

프로그래머스

 

풀이코드는 다음과 같습니다.

#include <string>
#include <vector>

using namespace std;

vector<int> solution(int brown, int yellow) {
    vector<int> answer;
    int total{brown+yellow};
    int col{0},row{0};
    for(int i{3};i<total/2;i++)
    {
        if(total%i==0)
        {
            col=i;
            row=total/col;
            if(2*(col+row)-4==brown)
            {
                answer.push_back(row);
                answer.push_back(col);
                break;
            }
        }
    }
    
    return answer;
}

이번 문제에서는 설명에 모든 것을 알려주지 않기 때문에 직접 알아내야하는 것들이 있습니다.

1. 노란색은 가운데에 있고 갈색은 테두리에만 존재한다.

2. 직사각형을 모두 감싸는 갈색 타일은 총 2(x+y)-4이다.

3. 갈색 타일이 노란색을 감싼다고 했으므로 세로 길이는 최소 3이상이다.

1과 3을 알아내는 데에는 얼마 걸리지 않았으나 2를 생각해내는 데에 시간이 걸렸던 것 같습니다.

직사각형을 감싸는 타일의 수가 왜 2(x+y)-4인지 간단히 설명하면

가로의 길이가 x이고 세로의 길이가 y인 직사각형이 있고 이 테두리를 가로,세로가 모두 1인 정사각형으로 둘러싸면

y개의 높이가 좌,우에 모두 있으므로 2y개가 필요하고 x개의 넓이가 상,하에 모두 있으므로 2x개가 필요하지만 각 모서리에 중복되기 때문에 4개를 제거해주어야 합니다.

따라서 테두리를 모두 감싸는 타일의 개수가 2x+2y-4개가 됩니다.

for문을 통해 조건을 확인하게 되면 작은 수부터 확인하기 때문에 자동적으로 문제의 조건인 '카펫의 가로 길이는 세로 길이와 같거나, 세로 길이보다 깁니다.' 가 해결됩니다.

문제를 읽고 직접 필요한 조건들을 찾아낸다면 해결할 수 있는 문제라고 생각합니다.