https://www.acmicpc.net/problem/1915
1915번: 가장 큰 정사각형
첫째 줄에 n, m(1 ≤ n, m ≤ 1,000)이 주어진다. 다음 n개의 줄에는 m개의 숫자로 배열이 주어진다.
www.acmicpc.net
dp문제다. 완전 탐색으로 시도했지만 역시나 시간 초과. 점화식을 생각해내는 데에 시간이 걸렸던 문제다.
풀이
최소한의 정사각형을 만들 수 있는 칸부터 시작해야 한다. 2차원 배열 map에 대해서 x와 y의 값이 모두 1 이상이고 map[x][y]의 값이 0보다 커야 한다. 해당 좌표의 상, 좌, 좌대각선 칸 중 최솟값 + 1로 갱신해나가면 된다.
map[x][y] = min(min(map[x-1][y], map[x][y-1]), map[x-1][y-1]) + 1
정답 코드
'Problem Solving > BOJ' 카테고리의 다른 글
| [1148] 단어 만들기 (0) | 2022.11.03 |
|---|---|
| [1195] 킥다운 (1) | 2022.11.02 |
| [1347] 미로 만들기 (0) | 2022.10.31 |
| [1388] 바닥 장식 (0) | 2022.10.31 |
| [1063] 킹 (1) | 2022.10.28 |