안녕하세요. 혀코입니다.
오늘은 특정 셀을 포함하는 모든 사각형의 개수를 구하는 방법에 대해서 알아보겠습니다.
별을 포함하는 직사각형의 개수는 두가지 방법으로 구할 수 있습니다.
첫째,
전체 사각형의 개수 - 별을 포함하지 않는 직사각형의 개수 + 별을 포함하지 않는 직사각형의 교차되는 직사각형의 개수
((4 + 3 + 2 + 1) * (3 + 2 + 1)) - (3 + 2 + 1) - 2(4 + 3 + 2 + 1) - ((2 + 1) * (3 + 2 + 1)) + ((2* (2 + 1)) + (2 * 1))
= 10 * 6 - 6 - 20 - 18 + 8
= 60 - 36 = 24
여기서 전체 사각형의 개수는 열이 4개일때, 4 + 3 + 2 + 1 값을 구하고, 행이 3개일때, 3 + 2 + 1 값을 구해서 열과 행의 값을 곱해주면, 전체 사각형의 개수를 구할 수 있습니다. 그래서 10 * 6 해서 60이 됩니다.
별을 포함하지 않는 직사각형의 개수는 첫째 열 3 + 2 +1 값과 첫째행과 셋째행 2(4 + 3 + 2 + 1) 값과 셋째열과 넷째열 (2 + 1) * (3 + 2 + 1) 의 값을 빼고
서로의 교차 직사각형인 첫째열의 첫째 행과 마지막행의 직사각형 2개를 다시 더하고 첫째행과 셋째행의 세번째와 네번째 직사각형 2 * (2 + 1) 의 값을 더해주면,
답 24를 구할 수 있습니다.
두번째 방법은 이보다 더 심플합니다.
둘째,
가로로 별을 포함하는 직사각형의 개수 * 세로로 별을 포함하는 직사각형의 개수
가로로 별을 포함하는 직사각형의 개수와 세로로 별을 포함하는 직사각형의 개수를 직접 세어 곱합니다.
포함하는 직사각형의 개수를 셀 때에는 직사각형 1개부터 2개 3개 4개 식으로 늘려나가면서 세는 것이 중요합니다.
6 * 4 = 24
이렇게 특정한 셀을 포함하는 직사각형의 갯수를 구하는 방법에 대해서 알아봤습니다.
유용하셨다면, 공감과 구독 부탁 드립니다.
감사합니다. :)
댓글