튜기's bloggggg

Cut Paper

Algorithm2015.09.09 20:03










★내가 푼 방식

우선 어떻게 이 사각형의 수들을 구할지 생각을 했다. 사각형의 크기가 0이거나 한변의길이^2 일때 두가지 경우이외에는 사각형을 잘라야 하는 케이스임을 알아냈고 이를 코드로 짜는건 어렵지 않았다. 

이문제는 분할정복법을 이용하여 풀었다.

우선 행렬의 가로인덱스, 세로인덱스를 함수에 넘겨주고 그 인덱스를 기준으로 1,2,3,4사분면 을 각각 계산하여 더하였다.

그리고 각각의 사분면이 같은 숫자만 포함하고 있는지 확인하고(위의 두가지경우) 모두 같은수면 1을 반환하고, 

다른숫자가 포함되있으면 다시 그 사분면을 4개로 나누어 계산하도록 재귀적으로 코드를 짯다.


★풀이 코드★






[출처] Cut Paper|작성자 튜기


저작자 표시
신고

Comment +0