티스토리 뷰

반응형

 

Leo가 길에서 본 카펫이 갈색 격자 테두리가 둘러져 있고 내용물은 노란색 격자로 채워져 있는데

Leo는 노란 격자 갯수와 갈색 격자 갯수만 기억하지만 카펫의 전체 크기는 기억하지 못한다. 

이거만 해도 기억력이 많이 좋은거 같지만 Leo는 여기서 멈추지 않는다...

Leo가 길에서 본 카펫의 노란색과 갈색 격자의 갯수를 이용해서 카펫의 전체 크기를 구하고 싶어하는 문제

 


문제의 조건

 

1. 갈색 격자 갯수 brown, 노란 격자 갯수 yellow가 주어짐

 

2. 카펫의 테두리는 갈색 격자로 둘러져 있음

즉 카펫의 최소 높이는 3이다. 

예시 그림과 같이 노란 격자를 최소 한 칸 포함하면서 갈색 격자로 테두리가 둘러지려면 최소 3칸이 필요하다. 

-> 이렇게 접근했어야 하는데 처음에는 최대 너비를 구해서 접근하는 바람에 계산식만 괜히 복잡해지고 답은 나오지 않고 엄청 헤멨다.

 

4. 갈색과 노란 격자의 갯수가 주어지기 때문에 저것들을 모두 더하면 카펫의 넓이를 구할 수 있다. 

전체 카펫의 넓이에서 최소 높이 3으로 나누면 카펫의 초기 너비값을 구할 수 있다. 

이제 갈색 격자의 갯수를 구해야 하는데,

노란 격자는 카펫의 안쪽에 연속해서 채워져있기 때문에 노란 격자의 갯수는 노란 격자가 차지하는 넓이와 같다는 걸 알 수 있다. 

그런데 카펫 전체의 너비 = 가로 방향으로 갈색 격자가 놓인 갯수, 높이 = 세로 방향으로 갈색 격자가 놓인 갯수이다.

즉 갈색 격자의 너비 = 노란 격자의 너비+2, 갈색 격자의 높이 = 노란 격자의 높이+2 라는 것을 알 수 있다.

그렇다는 것은 (카펫의 너비 - 2) * (카펫의 높이 - 2) 가 노란 격자의 갯수(넓이)와 같다면

실제 카펫의 너비와 높이를 구할 수 있게 된다. 

 


 

 

#include <string>
#include <vector>

using namespace std;

vector<int> solution(int brown, int yellow) {
    vector<int> answer;

    int height = 3; //초기값은 최소 높이 3으로 설정 
    while (true)
    {
        int width = (brown + yellow) / height;
        //(가로 - 2) * (세로 - 2) 가 yellow와 같으면 계산 끝~~
        if (yellow == (width - 2) * (height - 2))
        {
            answer.emplace_back(width);
            answer.emplace_back(height);
            break;
        }
        else //if 조건에 맞지 않으면 높이를 1씩 높여가면서 가로길이를 구한다. 
            height++;
    }

    return answer;
}
반응형
댓글
반응형
공지사항
최근에 올라온 글
최근에 달린 댓글
Total
Today
Yesterday
링크
«   2025/02   »
1
2 3 4 5 6 7 8
9 10 11 12 13 14 15
16 17 18 19 20 21 22
23 24 25 26 27 28
글 보관함