백준 알고리즘 1915 가장 큰 정사각형

안녕하세요.

전상수 입니다.

오늘은 가장 큰 정사각형 문제를 풀겠습니다.

입력이 들어왔을 때 1로 만들어 지는 가장큰 정사각형의 넓이를 구하면 되는 문제입니다.

 위와 같은 입력이 들어왔다고 예를 들어보겠습니다. 여기서 가장큰 정사각형의 길이는 2가 되겠죠.

어떻게 알수 있을까요? j,i 기준에서 세방향을 봅니다. 

세방향에서 각각 가지고 있는 정사각형 길이가 같다면 (j,i)에 이전 정사각형 길이 +1을 한 식으로 입력해 줍니다. 

아니라면 세방향 값중 가장 작은 값에 +1을 시켜줍니다.

위의 방식대로 풀어보면 

1 1 1  이라는 입력이 들어오면 DP에 저장 되는 값은 1 1 1 이 됩니다.

1 1 1                                                             1 2 2

1 1 1                                                             1 2 3

점화식을 세워보면 

1일때

DP[j][i] = min(DP[j-1][i], DP[j][i-1], DP[j-1][i-1]) 이 됩니다.

코드는 위와 같습니다.

DP는 설명하기가 너무 어려운것 같네요.. 질문있으시면 댓글 달아주세요!