백준 1915 가장 큰 정사각형

2017.10.31 ** 화요일 ** Solution - 1915(가장 큰 정사각형)

풀이방법: 동적계획법

문제보기

문제 해석

기억난다.. 처음 풀었던 당시에 엄청 끙끙..거렸다는 것을..

알고보면 상당히 쉬운 문제이나 , 당시에 그 아이디어까지 가는데

머리가 좋지 않아서 2시간정도 걸렸던것 같다..

그 당시 풀이보다 시간복잡도가 반이나 줄어서 이렇게 포스팅하게 되었다.

(더 익숙해졌길래 의아했는데 , 알고보니 카카오 모의테스트 였구나..)

풀이방식

처음 이 문제를 접했을때는, 무식하게 완탐하려고했다.. 그렇게 시간이 흐르고 흘러

코드를 보니 엄청 더럽고, 내가 잘못하고 있다는 것을 알게되어 생각을 더하게 되었다.

문제를 잘보면 직관적으로 1로 이루어진 4각형이 보인다. 우리는 저 크기를 골라 내야한다.

처음에 시도했던 방법은 왼쪽위의 끝점(0,0)부터 계산해야하나 했다. 그런데 그렇게 하다보면

어떻게 사각형을 판별해야하는지 의문이 생긴다.

그래서 그 다음으로는 매핑되는 점을 선택해서 돌려보았다. 뭔가 사각형으로 마지막점까지 갈 수가 있어졌다.

그렇다면 어떻게 계산을 할지 고민해보았다. 예제에 있는 사각형을 보고 좀 전에 사각형 판별법과 같이 생각해보면

판별되는 숫자를 1로 감싸고 있다. ?!-> 아 변이 2다 ..그렇다면 1은 변이 1로 생각할 수 있겠다!

그렇다면 판별되는 숫자를 2로 바꿔주면 2가 될것같다.

다시 해석해보자면 판별되는 숫자를 기준으로 그 숫자와 나머지 3개가 같으면 +1로 증가시켜준다(정사각형이기때문에!)

하지만 잘생각해보면 0에서 -> 1도 만들어야하고 , 각각 한칸당 넓이가 1인 정사각형이다.

그래서 3개의 공간 ( 왼쪽위 , 바로위 , 왼쪽)을 비교해서 가장 작은 수를 +1시킨다.(그래야 주위에 0이 잇을때 1인 정사각형을 만듬)

->map[i][j] = Math.min(map[i - 1][j - 1], Math.min(map[i - 1][j], map[i][j - 1])) + 1;

그렇게 판별되는 정사각형의 넓이를 계산하여 최대 사각형의 넓이 변수 (maxCnt)와 비교하여 마지막에 출력한다.

->maxCnt = maxCnt < map[i][j] ? map[i][j] : maxCnt;

: 좀 마지막에 시간이 걸렸다.. 오류가 계속났다. 왜 그런지살펴보니 maxCnt*maxCnt가 답인데, 그냥 maxCnt만 출력했다..주의하자..

코드전체보기