[BOJ] 백준 1915 가장 큰 정사각형 (C++)

문제 링크

www.acmicpc.net/problem/1915

1915번: 가장 큰 정사각형

카테고리

DP

문제 풀이

* DP[X][Y] = N : (X,Y)가 어떤 정사각형의 우측 아래 꼭지점일 때, 될 수 있는 정사각형들 중 최대 변의 길이는 N이다.

 

1. 만약 행이나 열의 idx가 0인 경우 (X == 0 || Y == 0)

    👉 DP[X][Y] = board[X][Y]

 

2. 인접한 위,좌상,왼쪽의 dp값 중 0이 있는 경우
    👉 DP[X][Y] = board[X][Y]

 

3. 인접한 위,좌상,왼쪽의 dp값이 모두 0이 아닌 경우
    👉 DP[X][Y] = min(DP[X-1][Y], DP[X-1][Y-1], DP[X][Y-1]) + 1

 

4. DP값 중 가잔 큰 수의 제곱을 리턴한다.

주의할 점

* DP식 세울 때 0행 Y열들, X행 0열들을 따로 분류해서 식을 세운다.

코드 (C++)

채점 결과

한마디

점화식을 세우면 무난하게 풀 수 있는 문제였다.

비슷한 문제를 프로그래머스에서 푼 기억이 있어서 쉽게 점화식이 눈에 들어왔다. 링크

풀어본 문제를 다시 풀 때는 좀 더 빠르게 풀도록 연습해야겠다. 😄